算法的效率

1. 考点：概述

1.1 基本概念

• 时间复杂度： 是指程序运行从开始到结束所需要的时间。

  • 分析方法：通常分析时间复杂度的方法是从算法中选取一种对于所研究的问题来说是基本运算的操作，以该操作重复执行的次数作为算法的时间度量。
  • 一般来说，算法中原操作重复执行的次数是规模 $n$ 的某个函数 $T(n)$。

• 空间复杂度：是指对一个算法在运行过程中临时占用存储空间大小的度量。

  • 一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小。

1.2 思考与案例

• 思考：求 $1+2+\cdots+100$ 的哪个算法更快？占用空间更少？

• 算法1：​int i = (1+100)*100/2;

  • 只要运算 1 次。
  • 需要 1 个变量。

• 算法2：​for 循环执行 100 次。

  • 要运算 $n$ 次。
  • 需要多个变量。

1.3 渐进时间复杂度

• 引入原因：由于许多情况下要精确计算 $T(n)$ 是困难的，因此引入了渐进时间复杂度在数量上估计一个算法的基本操作总数。一般讲时间复杂度，就是指渐进时间复杂度。
• 定义：如果存在两个常数 $c$ 和 $m$，对于所有的 $n$，当 $n \ge m$ 时有 $f(n) \le cg(n)$，则有 $f(n) = O(g(n))$。也就是说，随着 $n$ 的增大， $f(n)$ 渐进地不大于 $g(n)$。

1.4 示例与度量

• 例如：一个程序的实际执行时间为 $T(n) = 3n^3 + 2n^2 + n$，求其渐进时间复杂度。

• 随着 $n$ 不断增加，$2n^2 + n$ 的影响很小。时间主要由 $n^3$ 决定，则 $T(n)$ 的渐进时间复杂度就是 $O(n^3)$，把常量值去掉。

• 常见的对算法执行所需时间的度量：

  $$O(1) < O(\log_2 n) < O(n) < O(n \log_2 n) < O(n^2) < O(n^3) < O(2^n) < O(n!)$$

2. 考点：实例讲解

2.1 常数级时间复杂度 $O(1)$

• 单个语句

  • 如：​k = 0;

• 整个程序都只有顺序执行的语句，没有循环语句，或复杂函数的调用

void main() {
    char* x = "ABCADAB";
    int m = strlen(x);
    printf("len:%d\n", m);
}

2.2 时间复杂度 $O(n)$

• 单层循环

void main() {
    int i, j;
    k = 0;
    for(i = 0; i < n; i++) {
        b[i] = 0;
    }
}

2.3 时间复杂度 $O(n^2)$

• 双层循环

void main() {
    int i, s = 0, n = 1000;
    for(i = 1; i < n; i++)
        for(j = 1; j < n; j++)
            s += j;
    printf("结果为:%d", s);
}

2.4 $O(n^3)$ 依次类推：也就是三层循环了

2.5 时间复杂度 $O(\log_2 n)$

• 在有序数组中实现折半查找

int search(int array[], int n, int v)
{
    int left, right, middle;
    left = 0, right = n - 1;
    while (left <= right)
    {
        middle = (left + right) / 2;
        if (array[middle] > v)
        {
            right = middle - 1;
        }
        else if (array[middle] < v)
        {
            left = middle + 1;
        }
        else
        {
            return middle;
        }
    }
    return -1;
}

• 核心思想：每次查找，范围减半

  • 折半查找的原理是：每次拿数组中间的元素 ​array[middle] 和目标值 $v$ 比较：

    • 如果目标值小，就去左半区找。
    • 如果目标值大，就去右半区找。
    • 如果相等，直接返回。

  • 无论去左半区还是右半区，待查找的元素数量都会瞬间减少一半。

• 数学推导过程

  • 假设数组一共有 $n$ 个元素。
  • 第 1 次查找后，剩余元素最多为 $\frac{n}{2}$ 个。
  • 第 2 次查找后，剩余元素最多为 $\frac{n}{2^2}$ 个。
  • 第 3 次查找后，剩余元素最多为 $\frac{n}{2^3}$ 个。
  • ……
  • 第 $k$ 次查找后，剩余元素最多为 $\frac{n}{2^k}$ 个。
  • 最坏的情况是：一直找到最后只剩 1 个元素才找到（或者发现找不到）。
  • 所以，当剩下 1 个元素时：$\frac{n}{2^k} = 1$
  • 两边同时乘以 $2^k$：$n = 2^k$
  • 两边取以 2 为底的对数：$k = \log_2 n$
  • 这就意味着，最多只需要查找 $\log_2 n$ 次，就能把范围缩小到 1 个元素。因此，时间复杂度是 $O(\log_2 n)$。

• 举个直观的例子

  • 假设 $n = 8$：

    • 第 1 次查找，剩 4 个元素 ($8 \div 2$)
    • 第 2 次查找，剩 2 个元素 ($4 \div 2$)
    • 第 3 次查找，剩 1 个元素 ($2 \div 2$)
    • 结束。最多找了 3 次。

  • 而 $\log_2 8 = 3$，完全吻合。

2.6 时间复杂度 $O(n \log_2 n)$

• 典型代表：堆排序（利用大小顶堆实现排序）、快速排序、归并排序。

• 推导与理解逻辑：

  • 每次重建堆（或分治合并）的时间复杂度是 $\log_2 n$，$n$ 个元素基本上就是 $n \log_2 n$。
  • 每次从堆顶取出最大/最小元素后，需要重建堆。重建堆本质上是把根节点向下调整，调整的次数取决于树的高度，而 $n$ 个节点的完全二叉树高度为 $\log_2 n$。
  • 一共要取 $n$ 次，所以总时间复杂度是 $n \times \log_2 n = O(n \log_2 n)$。

2.7 时间复杂度 $O(2^n)$

• 典型代表：判断是否包含指定子序列、LCS（最长公共子序列）、钢管切割问题、暴力求所有子集，动态规划法自顶向下，时间复杂度都为 $O(2^n)$ 。

• 【判断是否包含指定子序列】例子： $a, b, c$数学计算与含义解析：

  • 这代表了“选或不选”的决策过程。

  • 假设有 3 个元素 $a, b, c$。我们要找出它所有的子集（或者判断它是否包含某个特定子序列）。对于每一个元素，我们都有 2 种选择：

    • 选它（状态记为 1）
    • 不选它（状态记为 0）

  • 那么：

    • 对于元素 $a$：有 2 种选择
    • 对于元素 $b$：有 2 种选择
    • 对于元素 $c$：有 2 种选择

  • 根据乘法原理，总共可能的情况就是：$2 \times 2 \times 2 = 2^3 = 8$ 种。

  • 推广到 $n$ 个元素：

    • 如果这里有 $n$ 个元素，每个元素都有“选”和“不选”两种可能，那么总的计算量就是 $n$ 个 2 相乘，即 $2^n$。
    • 这就是指数级时间复杂度 $O(2^n)$ 的数学来源。

• 【钢管切割的问题】经典案例：钢管切割问题（Rod Cutting Problem）

  • 问题描述：假设你有一根长度为 $n$ 的钢管，和一个价格表 $p[i]$（表示长度为 $i$ 的钢管能卖多少钱）。目标是如何切割这根钢管，使得卖出的总价格最高？

  • 举例说明（钢管长度 $n=4$）：

    • 价格表：长度 $1 \rightarrow 1$ 元，长度 $2 \rightarrow 5$ 元，长度 $3 \rightarrow 8$ 元，长度 $4 \rightarrow 9$ 元。

    • 切法与收益：

      • 不切：卖 $9$ 元
      • 切 1 和 3：$1 + 8 = 9$ 元
      • 切 2 和 2：$5 + 5 = 10$ 元（✅ 最优解）
      • 切 1, 1, 2：$1 + 1 + 5 = 7$ 元
      • 切 1, 1, 1, 1：$1 + 1 + 1 + 1 = 4$ 元

  • 为什么暴力递归是 **$O(2^n)$**​ ？

    • 决策过程：

      • 对于长度为 $n$ 的钢管，第一刀可以切在任意位置 $i$（$1 \le i \le n$）。
      • 切下长度为 $i$ 的一段，剩下的部分长度是 $n-i$，剩下的部分又面临同样的子问题。
      • 递归公式：$\text{MaxProfit}(n) = \max_{1 \le i \le n}(p[i] + \text{MaxProfit}(n-i))$。

    • 递归树结构（以 $n=4$ 为例）：

    • 为什么是指数级？

      • $n=1$ 时，1 种切法（不切）
      • $n=2$ 时，2 种切法（不切 / 切1+1）
      • $n=3$ 时，4 种切法
      • $n=4$ 时，8 种切法
      • ……
      • 当长度为 $n$ 时，总共有 $2^{n-1}$ 种切法。
      • 这就是指数爆炸。当 $n=40$ 时，$2^{39}$ 就已经超过 5000 亿了，计算机根本算不过来。

    • 关键问题：重复子问题（Overlapping Subproblems）

      • 递归树里的 $f(2)$ 被计算了很多次，$f(1)$ 更是被反复计算。这种重复子问题就是暴力递归效率极低的根本原因。
      • 总结：通过切法总数推导可知，其暴力递归的时间复杂度是 $O(2^{n-1})$（在渐进意义上即为 $O(2^n)$）。

• 【动态规划算法自顶而下】例子：树形结构图与决策树 / 子集树解析：

  • 这是一个没有画完的树状草图，它对应了左边 $a, b, c$ 的决策过程：

    • 第一层：对应元素 $a$。树从这个根节点开始，分出两条分支（左分支代表“选 $a$”，右分支代表“不选 $a$”）。
    • 第二层：对应元素 $b$。第一层分出的每个节点，又各自分出两条分支。
    • 第三层：对应元素 $c$。第二层分出的每个节点，再次各自分出两条分支。

  • 草图结构演示：

  • 				 (根)               
                    /    \        
               选a /      \ 不选a 
                  /        \          
             (节点1)      (节点2)          
             /    \        /    \     
        选b /      \不选b/      \不选b        
           /        \   /        \     
       (节点3)  (节点4)(节点5)  (节点6)      
        /  \     /  \   /  \     /  \    
       ...  ... ... ... ... ... ... ...  (继续对 c 进行分支)

  • 为什么这个树能解释 $O(2^n)$？

    • 树的深度是 $n$（对应 $n$ 个元素）。
    • 每一层节点的数量都会翻倍：第一层 1 个，第二层 2 个，第三层 4 个，第四层 8 个……
    • 到了第 $n$ 层，节点的数量就是 $2^{n-1}$ 个左右。
    • 如果要遍历整棵树（也就是找出所有可能的子集），算法需要访问的节点总数接近 $2^{n+1}-1$，这在数量级上也就是 $O(2^n)$。

2.8 常见时间复杂度的大小（快慢）关系与排序

$$O(1) < O(\log_2 n) < O(n) < O(n \log_2 n) < O(n^2) < O(n^3) < O(2^n) < O(n!)$$

• 左边是效率高（快），右边是效率低（慢）。

• 重点理解记忆倒数三个（图里用红字标注的重点）：

  • $O(2^n)$：指数级。比如求所有子集，每增加一个元素，计算量翻倍。$n$ 稍微大一点程序就跑不动了。
  • $O(n^a)$：多项式级，通常指 $a > 2$ 的情况。比如 $O(n^3)$，多层嵌套循环。
  • $O(n!)$：阶乘级。最典型的代表是旅行商问题（TSP）的暴力穷举解法，比如全排列问题。$n=10$ 时，计算量就超过 300 万次了。

2.9 考试快速记忆与对应表

• 看循环次数：

  • 单层循环 $\rightarrow O(n)$
  • 双层嵌套循环 $\rightarrow O(n^2)$
  • 三层嵌套 $\rightarrow O(n^3)$
  • 每次循环范围减半（如二分） $\rightarrow O(\log n)$
  • 循环里带二分，或者分治合并 $\rightarrow O(n \log n)$

• 经典算法对应表（直接背）：

  • 二分查找：$O(\log n)$
  • 冒泡 / 插入 / 选择排序：$O(n^2)$
  • 快速排序 / 归并排序 / 堆排序：$O(n \log n)$
  • 暴力求所有子集：$O(2^n)$
  • 暴力求全排列：$O(n!)$

3. 经典例题

3.1 题目一

题目：根据渐进分析，表达式序列：​**$n^4, \lg n, 2^n, 1000n, n^{2/3}, n!$** 从低到高排序为 ( )。

• A、$\lg n, 1000n, n^{2/3}, n^4, n!, 2^n$
• B、$n^{2/3}, 1000n, \lg n, n^4, n!, 2^n$
• C、$\lg n, 1000n, n^{2/3}, 2^n, n^4, n!$
• D、$\lg n, n^{2/3}, 1000n, n^4, 2^n, n!$

解析：

• 将给定的表达式按照增长速度从低到高进行渐进分析排序：

1. $\lg n$：对数阶，增长速度最慢。
2. $n^{2/3}$：幂次阶（指数为 $\frac{2}{3} \approx 0.67 < 1$），增长慢于线性阶。
3. $1000n$：线性阶（常数系数不影响渐进量级）。
4. $n^4$：多项式阶。
5. $2^n$：指数阶。
6. $n!$：阶乘阶，增长速度最快。

• 综合排序结果

$$\lg n < n^{2/3} < 1000n < n^4 < 2^n < n!$$

正确答案：D。

3.2 第二题

题目： 求解两个长度为 $n$ 的序列 $X$ 和 $Y$ 的一个最长公共子序列（如序列 ​ABCDAB​ 和 ​BDCABA​ 的一个最长公共子序列为 ​BCBA）可以采用多种计算方法。如可以采用蛮力法，对 $X$ 的每一个子序列，判断其是否也是 $Y$ 的子序列，最后求出最长的即可，该方法的时间复杂度为（ ）。经分析发现该问题具有最优子结构，可以定义序列长度分别为 $i$ 和 $j$ 的两个序列 $X$ 和 $Y$ 的最长公共子序列的长度为 $C[i,j]$，如下式所示。

$$C[i][j] = \begin{cases} 0 & \text{若 } i=0 \text{ 或 } j=0 \\ C[i-1,j-1]+1 & \text{若 } i,j>0 \text{ 且 } X_i=Y_j \\ \max(C[i-1,j],C[i,j-1]) & \text{其它} \end{cases}$$

采用自底向上的方法实现该算法，则时间复杂度为（ ）。

• 第一空：
  A、$O(n^2)$ B、$O(n^2 \lg n)$ C、$O(n^3)$ D、$O(n \cdot 2^n)$
• 第二空：
  A、$O(n^2)$ B、$O(n^2 \lg n)$ C、$O(n^3)$ D、$O(n \cdot 2^n)$

【解析】

本题考察的是最长公共子序列（LCS）算法的时间复杂度分析。

• 第一空（蛮力法） ：
  序列 $X$ 的长度为 $n$，其所有可能的子序列个数为 $2^n$（每个元素有选或不选两种状态）。对于 $X$ 的每一个子序列，都需要去判断它是否也是 $Y$ 的子序列，这个判断过程最坏情况下需要遍历 $Y$，时间复杂度为 $O(n)$。因此，蛮力法的总时间复杂度为 $O(n \cdot 2^n)$。对应选项为 D。
• 第二空（动态规划/自底向上法） ：
  根据题目给出的状态转移方程，采用自底向上的方法（通常指填表法）实现该算法时，需要计算一个二维数组 $C[i][j]$，其中 $i$ 的范围是 $0$ 到 $n$，$j$ 的范围也是 $0$ 到 $n$。这个二维表格的大小为 $(n+1) \times (n+1)$，即包含 $O(n^2)$ 个状态（单元格）。计算每一个状态 $C[i][j]$ 时，只需要进行常数次的比较和赋值操作（$O(1)$ 的时间）。因此，总的时间复杂度等于状态数量乘以单个状态的计算时间，即 $O(n^2) \times O(1) = O(n^2)$。对应选项为 A。

正确答案：D、A。

‍