1. 时间复杂度

O(1)

常见的就是直接访问一个数组中某个元素的内容
这种算法一般不会受到输入数据大小的影响

return array[i];

O(n)

线性时间复杂度，一般是遍历一阶数组中的所有元素
这会随着输入数据量的大小线性增大

O(log n)

对数时间复杂度，一般自常见的是用在对分查找。
或者常见的 m 叉树结构我们有 $O(log_m n)$ 的时间复杂度

O(n log n) - 线性对数时间复杂度

归并排序或快速排序。
说明：这些排序算法在最好或平均情况下的时间复杂度为n log n。
具体的算法的时间复杂度我们会在后面的细节讲解中提及.

O(n^2) - 平方时间复杂度

冒泡排序或选择排序。
说明：这类算法通常涉及双重循环，对每对输入元素都进行操作。
容易搞混的地方在于，我们看每一层循环都容易看出是 一阶复杂度，然后我们会认为直接加起来就是一阶求和还是一阶复杂度，这就不对了

冒泡排序的时间复杂度推导

从最差角度考虑，冒泡排序需要比较 + 替换相邻元素的次数是 $(n - 1) + \cdots + 1 = \frac{n(n-1)}{2}$
那么时间复杂度就是 $O(n^2)$

选择排序时间复杂度推导

从最差角度考虑，对于每一位变量都要从 m - 1 的位置开始选择，时间复杂度计算和 冒泡排序的相近
因此时间复杂度公式也是 $O(n^2)$

插入排序时间复杂度

从最差角度考虑，每一位都要执行m遍，计算公式和 冒泡一样
时间复杂度公式就是 $O(n^2)$

O(n^3) - 立方时间复杂度

示例：简单的三重循环，例如用于计算三维数据的直接处理。
说明：算法的执行时间随输入大小的立方增长。

O(2^n) - 指数时间复杂度

计算斐波那契数列的递归实现。
这类算法的运行时间随输入大小的指数级增长，通常用于解决递归分治问题。

斐波那契递归调用的时间复杂度

每次递归调用自身两次，对于每个 n 值，都生成了两个新的递归调用，这导致了指数级的增长。具体地，对于每一个 n，调用次数可以用二叉树的节点数来近似，其中树的深度为 n。
节点总数: 在这样的二叉树中，节点总数大约是 $2^0+2^1+2^2+…+2^{n−1}$，这是一个几何级数，其和为 $2^{n} - 1$
效率问题: 原因在于重复计算：在计算 $F(n)$ 时，会多次计算 $F(n−1)$、$F(n−2)$、$F(n−3)$ 等等。例如，F(n−1) 和 F(n−2) 会分别再计算 F(n−2)，这导致大量的重复劳动。

O(n!) - 阶乘时间复杂度

示例：旅行推销员问题的暴力求解算法。
说明：这种复杂度通常出现在需要穷举所有可能情况的算法中。

大 O 的计算法则

加法规则

当一个算法由多个连续步骤组成，每个步骤有不同的时间复杂度时，总的时间复杂度是各个步骤时间复杂度的和。例如，如果一个算法的第一部分有时间复杂度 $O(n)$ ，第二部分有时间复杂度 $O(n^2)$，则整个算法的时间复杂度将是这两者的和。

• 规则：$O(f(n))+O(g(n))=O(\max⁡(f(n),g(n)))$
• 例子：如果算法的一个部分是 $O(n)$ ，另一个部分是 $O(n^2)$，那么总的时间复杂度是 $O(n^2)$

乘法规则

当算法涉及到嵌套的循环或多个步骤的乘积时，总的时间复杂度是各个复杂度的乘积。例如，如果一个函数调用（时间复杂度为 O(n) 在另一个 O(m) 复杂度的循环中，总的时间复杂度是这两者的乘积。

• 规则：O(f(n))×O(g(n))=O(f(n)×g(n))
• 例子：如果一个算法包含一个外部循环 O(n) 和一个内部循环 O(m)，则总的时间复杂度是 O(n×m)