如何计算简单的时间复杂度：以分治为例

从渐进记号、操作计数和递归树出发，分析最大子段和、排序、快速幂与筛法的时间复杂度。

在本周的课程中，我们学习了用分治处理排序、最大子段和等问题。课后有同学问我，为什么最大子段和的分治算法是 \(O(N\log N)\)，平时也发现有些同学对“时间复杂度”还不太熟悉。所以写了这篇材料作为拓展分享。

什么是时间复杂度分析

时间复杂度分析的不是某台电脑实际跑了多少秒，而是输入规模增长时，基本操作次数如何增长。同样长度的输入也可能让算法走不同的路径，因此常区分最坏情况 \(T_{\mathrm{worst}}(N)\) 和平均情况 \(T_{\mathrm{avg}}(N)\)；谈平均情况时，还要说明输入按什么分布出现。下文以及平时没有特别说明时，分析的都是最坏情况。

数学基础：渐进记号

设 \(T(N)\ge 0\)，比较用的函数 \(f(N)>0\)（至少在足够大的 \(N\) 上成立）。这些记号描述的是充分大的 \(N\)，差不多可以近似理解成趋向无穷。

记号	严格定义	直观含义
\(T(N)=O(f(N))\)	存在 \(c>0,N_0\)，使 \(N\ge N_0\) 时 \(T(N)\le cf(N)\)	渐进上界
\(T(N)=\Omega(f(N))\)	存在 \(c>0,N_0\)，使 \(N\ge N_0\) 时 \(T(N)\ge cf(N)\)	渐进下界
\(T(N)=\Theta(f(N))\)	同时满足 \(O(f(N))\) 和 \(\Omega(f(N))\)	同阶，即上下界都紧
\(T(N)=o(f(N))\)	对任意 \(\varepsilon>0\)，充分大的 \(N\) 都有 \(T(N)\le\varepsilon f(N)\)	严格低阶

我们习惯写等号，但 \(T(N)=O(f(N))\) 实际表示 \(T\) 属于由 \(f\) 给出的上界类别，不是两个函数相等。

我个人更喜欢用比值理解：如果 \(\lim_{N\to\infty}T(N)/f(N)=0\)，那么 \(T=o(f)\)；如果极限是一个有限的正常数，那么 \(T=\Theta(f)\)。例如 \(N^2=O(N^3)\) 当然正确，但 \(N^2=\Theta(N^2)\) 给出的界更紧。\(T=O(f)\) 的意思是 \(f\) 给 \(T\) 提供上界，不是说 \(f\) 是下界。

计算时常用的几条规则

设各段耗时都非负。如果 \(T_1=O(f)\)、\(T_2=O(g)\)，顺序执行的总耗时满足

$$

T_1+T_2=O(f+g)=O({f,g}).

$$

若已知 \(T_1=\Theta(f)\)、\(T_2=\Theta(g)\)，才能进一步写成 \(\Theta(\max\{f,g\})\)。

若 \(T(N)\) 是最高次项系数为正的 \(k\) 次多项式，则 \(T(N)=\Theta(N^k)\)。因此 \(O(N^2+N)\) 没有错，只是通常写成更简洁的 \(O(N^2)\)；\(O(3N^2)\) 也同理。对数的底数只差常数倍，在渐进记号中通常省略。

数操作次数

对于几种基本情况，规则如下 - 顺序语句：把各段时间相加；非负函数的渐进上界由增长最快的一项决定。 - 分支：最坏情况取可能执行的分支中较慢的一个，再加上判断条件本身的开销。 - 循环：循环体成本乘迭代次数，前提是每轮成本大致相同；若不同，就逐轮求和。 - 嵌套循环：内层次数若依赖外层变量，不能机械地把两个上限相乘。

例如内层每轮分别执行 \(1,2,\ldots,N\) 次，总次数为

$$

_{i=1}^{N}i=2=(N2).

$$

最大子串和

给定整数序列 \(A_1,\ldots,A_N\)，其中可以有负数；求非空连续子段的最大和

$$

M={1ijN}{k=i}^{j}A_k.

$$

全负数时答案是最大的那个负数，以下都假定 \(N\ge1\)。

穷举法

共有 \(N(N+1)/2=O(N^2)\) 个端点对 \((i,j)\)。如果对每个端点对都从头算一次 \(\sum_{k=i}^{j}A_k\)，最坏会做

$$

{i=1}^{N}_{j=i}{N}(j-i+1) ={}^{N}(N-+1) =6 =O(N^3)

$$

次加法。

但固定左端点 \(i\) 后，右端点向右移动时只需把新元素加进已有的和，没必要重算前面的元素：

def max_sum_quadratic(arr):
    best = arr[0]
    for i in range(len(arr)):
        total = 0
        for j in range(i, len(arr)):
            total += arr[j]
            best = max(best, total)
    return best

现在每个端点只做常数次工作，故时间为 \(O(N^2)\)，额外空间为 \(O(1)\)。

分治

把区间从中间切开，最大子段只有三种位置：完全在左、完全在右、横跨中点。前两种交给递归；跨中点的答案等于“左边以中点左侧结束的最大后缀”加“右边从中点右侧开始的最大前缀”。两边各扫一遍，当层成本是 \(O(N)\)。单元素直接返回自身，于是

$$

T(N)=T(N/2)+T(N/2)+O(N), T(1)=O(1).

$$

递归树有 \(O(\log N)\) 层，每层的区间互不重叠、总长度为 \(N\)，因此每层工作量为 \(O(N)\)，总时间

$$

T(N)=O(NN).

$$

前缀和

令 \(P_0=0\)，\(P_j=\sum_{k=1}^{j}A_k\)，则

$$

{k=i}^{j}A_k=P_j-P{i-1}.

$$

固定右端点 \(j\) 时，要让它最大，只需找到此前最小的前缀和：

$$

{1ij}{k=i}^{j}A_k =P_j-_{0t<j}P_t.

$$

从左到右维护 \(P_j\) 和此前最小的 \(P_t\)，每个元素只处理一次：

def max_sum_prefix(arr):
    if not arr:
        raise ValueError("需要非空列表")
    prefix = min_prefix = 0
    best = arr[0]
    for x in arr:
        prefix += x
        best = max(best, prefix - min_prefix)
        min_prefix = min(min_prefix, prefix)
    return best

先用旧的最小前缀更新答案，再把当前前缀纳入最小值，才保证 \(t<j\)、子段非空。若顺序反过来，当前前缀可减去自己得到 \(0\)，全负数时就可能答错。时间 \(O(N)\)，额外空间 \(O(1)\)。

Kadane

另一种想法是先不考虑任意终点，只考虑必须以当前位置结尾的最大和 \(E_i\)。这样的子段要么从 \(A_i\) 重新开始，要么接在前一个最优后缀后面：

$$

E_1=A_1,E_i=(A_i,E_{i-1}+A_i),M=_{1iN}E_i.

$$

def max_sum_kadane(arr):
    if not arr:
        raise ValueError("需要非空列表")
    current = best = arr[0]
    for i in range(1, len(arr)):
        current = max(arr[i], current + arr[i])
        best = max(best, current)
    return best

它与前缀和其实是在描述同一个量：\(E_j=P_j-\min_{0\le t<j}P_t\)。两者都只扫描一次，时间 \(O(N)\)，额外空间 \(O(1)\)。

方法	时间	关键原因
每个区间重新求和	\(O(N^3)\)	同一段和反复计算
固定左端点，累加右端点	\(O(N^2)\)	端点对共有二次方个
分治	\(O(N\log N)\)	对数层，每层线性扫描
前缀和 / Kadane	\(O(N)\)	每个元素只处理常数次

再看几个经典算法

冒泡排序与插入排序

标准冒泡排序的比较次数为 \((N-1)+(N-2)+\cdots+1=N(N-1)/2\)，最坏时间 \(O(N^2)\)。若设置“本趟没有交换就提前结束”，已排序输入只需一趟，最好时间 \(O(N)\)；没有这个判断时，最好情况也仍会做二次方次比较。

插入排序把新元素向左插进已排序的前缀。第 \(i\) 次最多移动 \(i\) 个元素，最坏总移动次数 \(\sum_{i=1}^{N-1}i=O(N^2)\)；已排序时每次只比较少数几次，最好 \(O(N)\)。若输入是均匀随机排列，平均逆序对数为 \(N(N-1)/4\)，每个逆序对都对应一次向右移动，所以平均时间也是 \(O(N^2)\)。

归并排序与快速排序

归并排序把两半都排好，再用线性时间合并：

$$

T(N)=2T(N/2)+O(N)=O(NN).

$$

奇数长度时两半差一个元素，不改变结论；合并需要 \(O(N)\) 额外空间。

快速排序先分区。每层分区花 \(O(N)\)；若每次分得接近一半，与归并有同样的 \(O(N\log N)\)。若总选到最小或最大值，如“首元素作基准”遇到已排序输入，就有

$$

T(N)=T(N-1)+O(N)=O(N^2).

$$

因此“快排是 \(O(N\log N)\)”若未说明条件，只能理解为平均或期望表现，不是最坏保证。随机选基准、元素互异时，还能从比较概率看出期望复杂度：排序后排名相隔 \(d\) 的一对元素被比较的概率是 \(2/(d+1)\)，全部元素对的期望比较次数为

$$

_{d=1}^{N-1}(N-d)=O(NN).

$$

快速幂

计算 \(a^m\) 时，若每次只乘一个 \(a\)，需要 \(O(m)\) 次乘法。利用 \(a^{2q}=(a^q)^2\)，指数每轮折半：

def fast_power(a, m):
    if m < 0:
        raise ValueError("这里约定指数非负")
    result = 1
    while m > 0:
        if m % 2 == 1:
            result *= a
        a *= a
        m //= 2
    return result

循环次数是 \(\lfloor\log_2 m\rfloor+1\)（\(m\ge1\)），每轮做常数次乘法，所以按乘法次数计为 \(O(\log m)\)。若整数非常大，单次大整数乘法并非固定时间；这时还要单独考虑整数位数带来的成本。

Eratosthenes素数筛

筛法先假设 \(0\) 到 \(N\) 中的数是素数，再对每个尚未被划掉的 \(p\le\sqrt N\)，从 \(p^2\) 开始划掉 \(p\) 的倍数。更小的倍数已被更小的质因子处理过。

初始化花 \(O(N)\)；划去倍数的次数可写成

$$

_{} (Np-p+1).

$$

用“素数倒数和”\(\sum_{p\le x}1/p=\log\log x+O(1)\) 这个很巧妙的结论，再注意 \(\sum_{p\le\sqrt N}p\le N\)，划去倍数的总次数就是 \(N\log\log N+O(N)\)。因此标准筛法的时间是 \(O(N\log\log N)\)，布尔表占 \(O(N)\) 空间。这里的 \(\log\log N\) 不是因为写了两层循环，而是来自只对素数 \(p\) 枚举倍数。

思考题

先不要看到两层循环就直接把循环次数相乘。读下面的程序，假设输入满足 \(1\le n\le 10^7\)：

#include <bits/stdc++.h>
using namespace std;

int a[10000005];
int main() {
    int n;
    cin >> n;
    int cnt = 0;
    for (int i = 2; i <= sqrt(n); i++) {
        int cc = i * i;
        if (a[cc] == 0) {
            a[cc]++;
            for (int i = cc; i <= n; i += cc) {
                a[i] = 1;
            }
        }
    }
    for (int i = 4; i <= n; i++) {
        cnt += a[i];
    }
    cout << n - cnt;
    return 0;
}

1. 手推 \(n=10\)：程序输出什么？它实际上在统计哪类整数？
2. 什么样的 \(i\) 会让 if (a[cc] == 0) 成立？为什么内层循环不能简单按“外层次数 \(\times\) 内层最多次数”估计？
3. 把内层循环的总执行次数写成求和式，给出程序的时间复杂度上界。

最后想提醒的一点

分析复杂度时，我觉得最有用的顺序是：先说清输入规模和所数的操作，再把循环次数写成和式，或把递归写成递推式，最后才化简成渐进记号。 只看到“两层循环”就写 \(O(N^2)\)，或看到“折半”就写 \(O(\log N)\)，都可能漏掉循环边界、递归分支，以及每一层实际做的工作。

参考资料

• Mark Allen Weiss，《数据结构与算法分析》。
• FIP W07 课程材料：《26FIP7 分治算法.pdf》