评估方法

实际测试：在计算机上运行算法并监控其运行时间和内存占用来进行的，但存在测试环境的干扰因素和资源消耗。

**理论估算：**渐近复杂度分析是一种评估算法效率的方法，它通过计算来预测随着输入数据量增加，算法处理时间或内存使用的变化趋势，而不是关注具体的处理时间或内存大小。

时间复杂度：

是衡量算法运行时间的一个指标，它反映了算法运行时间随着输入数据量的增加而增长的趋势。时间复杂度分析统计的不是算法运行时间，而是算法运行时间随着数据量变大时的增长趋势。

• 最差时间复杂度（Worst-Case Time Complexity）:用大 O 记号（O-notation）来表示；
• 最佳时间复杂度（Best-Case Time Complexity）：用大 Omega 记号（Ω-notation）来表示；
• 平均时间复杂度（Average-Case Time Complexity）：用大 Theta 记号（Θ-notation）来表示。

函数渐近上界

如果存在正实数 c 和实数 n_0，使得对于所有的 n > n_0，算法的执行步骤数 T(n) 小于或等于 c 乘以某个函数 f(n)，即：

$$T(n) \leq c \cdot f(n) \quad \text{对于所有的 } n > n_0$$

那么我们就说 f(n) 是 T(n) 的一个渐近上界，记作：

$$T(n) = O(f(n))$$

这里的 O 符号被称为大 O 记号，它表示 T(n) 的增长速度被 f(n) 的增长速度所限制。

推算方法

（1）统计操作数量：

• 忽略常数项、所有系数；
• 循环嵌套时使用乘法：外层循环的次数与内层循环的次数相乘**，得到总的操作数量。**

（2）判断渐近上界：

• 时间复杂度由操作数量中最高阶的项来决定。

常见类型

**线性阶：**通常出现在单层循环中； **平方阶：**嵌套循环中； **指数阶：**指数阶常出现于递归函数中； **对数阶：**也常出现于递归函数中； **线性对数阶：**常出现于嵌套循环中，两层循环的时间复杂度分别为O(logn)和O(n); **阶乘阶:**阶乘通常使用递归实现。

空间复杂度

用于衡量算法占用内存空间随着数据量变大时的增长趋势。

**空间复杂度的组成：**输入空间、暂存空间和输出空间。暂存空间可以进一步划分为暂存数据、栈帧空间和指令空间。

**推算方法：**空间复杂度的推算方法与时间复杂度大致相同，只需将统计对象从“操作数量”转为“使用空间大小”。通常只关注最差空间复杂度：（1）以最差输入数据为准；（2）以算法运行中的峰值内存为准。

**常数阶 O(1) ：**常见于数量与输入数据大小 n 无关的常量、变量、对象。 **线性阶 O(n) ：**常见于元素数量与输入数据大小 n 成正比的数组、链表、栈、队列等。 **平方阶 O(n^2) ：**常见于矩阵和图，元素数量与输入数据大小 n 成平方关系。 **指数阶 O(2^n) ：**常见于二叉树等结构。观察图 2-19，层数为 n 的“满二叉树”的节点数量为 2^n - 1，占用 O(2^n) 空间。 **对数阶 O(log n) ：**常见于分治算法，例如归并排序。输入长度为 n 的数组，每轮递归将数组从中点处划分为两半，形成高度为 log n 的递归树，使用 O(log n) 栈帧空间。