ByteByteGo整理的常见时间复杂度示意图。

1 - O(1)

这是常数时间复杂度。无论输入规模多大，运行时间保持不变。例如，通过索引访问数组中的元素，以及在哈希表中插入/删除元素。

2 - O(n)

线性时间复杂度。运行时间与输入规模成正比增长。例如，在无序数组中查找最大或最小元素。

3 - O(log n)

对数时间复杂度。随着输入规模增长，运行时间增加得很慢。例如，对有序数组进行二分查找，以及在平衡二叉搜索树上的操作。

4 - O(n^2)

平方时间复杂度。运行时间随着输入规模呈指数增长。例如，简单的排序算法如冒泡排序、插入排序和选择排序。

5 - O(n^3)

立方时间复杂度。随着输入规模增大，运行时间急剧增加。例如，使用朴素算法对两个稠密矩阵进行相乘。

6 - O(n logn)

线性对数时间复杂度。这是线性增长和对数增长的结合。例如，高效的排序算法如归并排序、快速排序和堆排序。

7 - O(2^n)

指数时间复杂度。每增加一个输入元素，运行时间会翻倍。例如，递归算法通过将问题分解为多个子问题来解决。

8 - O(n!)

阶乘时间复杂度。运行时间随着输入规模迅速攀升。例如，排列生成问题。

9 - O(sqrt(n))

平方根时间复杂度。运行时间与输入的平方根成比例增加。例如，范围搜索，如埃拉托色尼筛法用于找到所有小于 n 的质数