港中深 CSC5001 课程笔记｜从循环到递归：算法复杂度分析入门

写在前面

CSC5001 第一周主要讨论算法复杂度分析。相比本科数据结构课程里直接判断复杂度，这里更强调从执行次数、求和或递推关系出发，给出较严格的渐进分析。本文整理 Lecture 1 和 Tutorial 1 中最常用的分析方法。

算法复杂度 ​O(n^2)、​\Omega(n^2)、​\Theta(n^2)

三种算法复杂度：

​O(n^2)：至多是这个量级，upper bound

​\Omega(n^2)：至少是这个量级，lower bound

​\Theta(n^2)：上下都卡住了，准确的渐进量级 / tight bound

日常语境中，一般直接称Big-O 为算法复杂度，但是在CSC5001中，算法复杂度要求有数学语境上的严格的区分。

举个栗子：

假如一个算法实际复杂度是

那么下面这些话其实都是真的：

因为 Big-O 只是在说“我能找一个上界把你罩住”。

但我们显然不会说：

这个算法复杂度是 ​O(n^{100})。

虽然数学上没错，但这答案烂得没什么信息。

而：

是在说：

它确确实实就是 ​n^2 这个增长级别。

需要掌握的数学和式

三个常用和式：

具体分析——双层循环

第一题：

for i = 1 to n:
    for j = 1 to i:
        s += 1

分析这段代码的复杂度。

这题非常简单，具体分析：

当外层的 ​i 取不同值时，内层 ​j 的取值和实际执行次数如下：

总和：

固定外层的 ​i，内层执行 ​i 次，所以可以写成

For a fixed ​i, the inner loop executes ​i times. Therefore, the total number of executions is

\sum_{i=1}^{n}i=\frac{n(n+1)}{2}.

Hence, the running time is ​\Theta(n^2).

第二段代码，难度升级下：

for i = 1 to n:
    j = i
    while j <= n:
        s += 1
        j += i

照样固定外层 ​i 来具体分析：

所以对于某个固定的 ​i，内层循环执行

次。

为什么是这个次数？

固定 ​i 后，​j 取值就是：

i,\,2i,\,3i,\,4i,\dots

问题变成找最大的整数 ​k，使得

ki\le n.

两边除以 ​i：

k\le \frac{n}{i}.

因为 ​k 必须是整数，所以最大的 ​k 就是

\boxed{\left\lfloor \frac{n}{i}\right\rfloor}.

然后把所有 ​i 的工作量加起来：

粗略地说，

先无视 floor：

而

所以

此处 ​H_n 即调和数：harmonic number

严谨版本：

把 ​i=1 到 ​n 全加起来：

于是

而

所以左右两边主导项都是 ​n\log n，那个额外的 ​-n 对渐进阶没有影响，于是：

完整解答：

For a fixed ​i, the inner loop starts with ​j=i and increases ​j by ​i in each iteration. Therefore, the inner loop executes ​\lfloor n/i\rfloor times.

Hence, the total number of executions of s += 1 is

T(n)=\sum_{i=1}^{n}\left\lfloor\frac{n}{i}\right\rfloor.

Since

\frac{n}{i}-1\le\left\lfloor\frac{n}{i}\right\rfloor\le\frac{n}{i},

we have

nH_n-n\le T(n)\le nH_n,

where ​H_n=\sum_{i=1}^{n}1/i=\Theta(\log n).
Therefore,

\boxed{T(n)=\Theta(n\log n)}.

递归问题

tutorial 原题：

Let your algorithm be recursive: to compute the result for n, it first computes the result for n - 1 with overhead n; computation at unit has a unit time. Aka T (n) = T (n - 1) + n, T (1) = 1. Determine the complexity.

解法：拆开化简

如果 ​T(1) = 1：

所以：

变种题目：

Let your algorithm be recursive: to compute the result for n, it first computes the result for n/2 with overhead 1; computation at unit has a unit time. Aka ​T(n)=T(\lfloor n/2\rfloor)+1, ​T(1)=1. Determine the complexity.

解法：同样拆开化简

机械代入原式：

先暂时忽略 floor，看成

因为递推式对任何规模都成立，所以可以逐层展开：

真正关键的是：什么时候停？

base case 是 ​T(1)=1，所以你要让

也就是

所以

因此：

算法纠错，原题：

二分搜索算法

binary_search(a, x, l, r):
    if l > r: return NOT_FOUND
    m = floor((l + r) / 2)
    if a[m] == x: return m
    if a[m] < x: return binary_search(a, x, m + 1, r)
    else: return binary_search(a, x, l, m - 1)

题目的分析

1. At each recursive call, the algorithm examines one element.
2. However, the recursive call may still have to search almost the entire remaining array.
3. In the worst case, the target is absent, so the algorithm continues until the interval becomes empty.
4. Therefore it makes at most ​n recursive calls.
5. Hence the complexity is ​\Theta(n).

请寻找上题的谬误之处。

谬误之处在于：However, the recursive call may still have to search almost the entire remaining array

实际上：

At each recursive call, the search interval is reduced to about half of its previous size.

完整解答：

At each recursive call, the search interval is reduced to about half of its previous size. Therefore, the running time satisfies

T(n)=T(\lfloor n/2\rfloor)+\Theta(1).

In the worst case, the target is absent, so the algorithm continues until the search interval becomes empty. Since the interval size is halved at each recursive call, the number of recursive calls is ​\Theta(\log n). Hence, the running time is

\Theta(\log n).

总结

经过上述分析，可以得模板如下：

循环题

For a fixed ​i, the inner loop executes ... times.
Therefore, the total number of executions is

T(n)=\sum ...

Hence,

T(n)=\Theta(...).

递归题

The running time satisfies

T(n)=...

Unrolling the recurrence,

T(n)=...

The recursion stops when ...
Hence,

T(n)=\Theta(...).

需要记住的就是分析方法和常用和式。

小练习

for i = 1 to n:
    j = 1
    while j <= i:
        s += 1
        j *= 2

试分析这段代码的复杂度。

答案：

For a fixed ​i, the inner loop executes

\lfloor\log_2 i\rfloor+1=\Theta(\log i)

times, since ​j doubles in each iteration. Therefore, the total number of executions is

\sum_{i=1}^{n}\Theta(\log i).

Since

\sum_{i=1}^{n}\log i=\Theta(n\log n),

the running time is

\boxed{\Theta(n\log n)}.