复杂度分析

复杂度分析：

• 渐近复杂度分析（asymptotic complexity analysis），简称复杂度分析。

• 定义：

  • 复杂度分析能够体现算法运行所需的时间和空间资源与输入数量级之间的关系；
  • 它描述了随着输入数据量级的增加，算法执行所需时间和空间的增长趋势。

• 复杂度分析的三个重点：

  • 时间和空间资源：分别对应时间复杂度、空间复杂度
  • 随着输入数据大小的增加：意味着复杂度反映算法运行效率与输入数据体量之间的关系
  • 时间和空间的增长趋势：表示复杂度分析关注的不是运行时间或占用空间的具体值，而是时间或空间增长的“快慢”。

1. 最差复杂度、最佳复杂度、平均复杂度

• 在实际中很少使用最佳时间复杂度，因为通常只有在很小概率下才能达到，可能会带来一定的误导性。
• 而最差时间复杂度更为实用，因为它给出了一个效率安全值，让我们可以放心地使用算法。
• 平均时间复杂度可以体现算法在随机输入数据下的运行效率，用 $\Theta$ 记号来表示。
• 通常使用最差时间复杂度作为算法效率的评判标准

2. 时间复杂度：

• 时间复杂度分析统计的不是算法运行时间，而是算法运行时间随着数据量变大时的增长趋势

实践经验：

1. 只关注循环执行次数最多的一段代码
2. 加法法则：总复杂度等于量级最大的那段代码的复杂度
3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

常见时间复杂度：

• 设输入数据大小为 $n$ ，常见的时间复杂度类型如下图所示（按照从低到高的顺序排列）

$$\begin{aligned} O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n) < O(n!) \newline \text{常数阶} < \text{对数阶} < \text{线性阶} < \text{线性对数阶} < \text{平方阶} < \text{指数阶} < \text{阶乘阶} \end{aligned}$$

* 常数阶 $O(1)$ * 常数阶的操作数量与输入数据大小 $n$ 无关，即不随着 $n$ 的变化而变化。

• 对数阶 $O(\log n)$

  • 与指数阶相反，对数阶反映了“每轮缩减到一半”的情况。设输入数据大小为 $n$ ，由于每轮缩减到一半，因此循环次数是 $\log_2 n$ ，即 $2^n$ 的反函数。
  • 对数阶也常出现于递归函数中。
  • 对数阶常出现于基于分治策略的算法中，体现了“一分为多”和“化繁为简”的算法思想。它增长缓慢，是仅次于常数阶的理想的时间复杂度。

• 线性阶 $O(n)$

  • 线性阶的操作数量相对于输入数据大小 $n$ 以线性级别增长。
  • 线性阶通常出现在单层循环中。
  • 遍历数组和遍历链表等操作的时间复杂度均为 $O(n)$ ，其中 $n$ 为数组或链表的长度：

• 线性对数阶 $O(n \log n)$

  • 线性对数阶常出现于嵌套循环中，两层循环的时间复杂度分别为 $O(\log n)$ 和 $O(n)$ 。
  • 主流排序算法的时间复杂度通常为 $O(n \log n)$ ，例如快速排序、归并排序、堆排序等。

• 平方阶 $O(n^2)$

  • 平方阶的操作数量相对于输入数据大小 $n$ 以平方级别增长。
  • 平方阶通常出现在嵌套循环中
  • 例如冒泡排序。外层循环和内层循环的时间复杂度都为 $O(n)$ ，因此总体的时间复杂度为 $O(n^2)$ ：

• 指数阶 $O(2^n)$

  • 生物学的“细胞分裂”是指数阶增长的典型例子：初始状态为 $1$ 个细胞，分裂一轮后变为 $2$ 个，分裂两轮后变为 $4$ 个，以此类推，分裂 $n$ 轮后有 $2^n$ 个细胞。
  • 指数阶常出现于递归函数中。
  • 指数阶的复杂度一般不可接受，通常需要使用动态规划或贪心算法等来解决。

• 阶乘阶 $O(n!)$

  • 阶乘阶对应数学上的“全排列”问题。给定 $n$ 个互不重复的元素，求其所有可能的排列方案。
  • 阶乘通常出现在递归实现中

3. 空间复杂度：

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

算法使用空间：

• 输入空间：用于存储算法的输入数据。

• 暂存空间：用于存储算法在运行过程中的变量、对象、函数上下文等数据。进一步划分：

  • 暂存数据：用于保存算法运行过程中的各种常量、变量、对象等。
  • 栈帧空间：用于保存调用函数的上下文数据。系统在每次调用函数时都会在栈顶部创建一个栈帧，函数返回后，栈帧空间会被释放。
  • 指令空间：用于保存编译后的程序指令，在实际统计中通常忽略不计。

• 输出空间：用于存储算法的输出数据。

• 空间复杂度分析哪些空间：

  • 通常统计暂存数据、栈帧空间和输出数据三部分，只关注最差空间复杂度
  • 在递归函数中，需要注意统计栈帧空间

常见空间复杂度：

• 设输入数据大小为 $n$ ，下图展示了常见的空间复杂度类型（从低到高排列）。

$$\begin{aligned} O(1) < O(\log n) < O(n) < O(n^2) < O(2^n) \newline \text{常数阶} < \text{对数阶} < \text{线性阶} < \text{平方阶} < \text{指数阶} \end{aligned}$$

• 常数阶 $O(1)$

  • 常数阶常见于数量与输入数据大小 $n$ 无关的常量、变量、对象。
  • 在循环中初始化变量或调用函数而占用的内存，在进入下一循环后就会被释放，因此不会累积占用空间，空间复杂度仍为 $O(1)$ ：

• 线性阶 $O(n)$

  • 线性阶常见于元素数量与 $n$ 成正比的数组、链表、栈、队列以及递归函数中：
  • 函数的递归深度为 $n$ ，即同时存在 $n$ 个未返回的 recur() 函数，使用 $O(n)$ 大小的栈帧空间：

• 平方阶 $O(n^2)$

  • 平方阶常见于矩阵和图，元素数量与 $n$ 成平方关系：

• 指数阶 $O(2^n)$

  • 指数阶常见于二叉树。观察下图，层数为 $n$ 的“满二叉树”的节点数量为 $2^n - 1$ ，占用 $O(2^n)$ 空间：
  • 

• 对数阶 $O(\log n)$

  • 对数阶常见于分治算法。
  • 例如归并排序，输入长度为 $n$ 的数组，每轮递归将数组从中点处划分为两半，形成高度为 $\log n$ 的递归树，使用 $O(\log n)$ 栈帧空间

4.权衡时间与空间

• 降低时间复杂度通常需要以提升空间复杂度为代价，反之亦然。
• 牺牲内存空间来提升算法运行速度的思路称为“以空间换时间”；反之，则称为“以时间换空间”。
• 在大多数情况下，时间比空间更宝贵，因此“以空间换时间”通常是更常用的策略。当然，在数据量很大的情况下，控制空间复杂度也非常重要。