3.1 复杂度增长与算法成本

为什么要先讲复杂度

CSCI2520 的讲义一开始先讲 growth，而不是先讲 micro-optimization，是有 原因的。当输入规模 n 变大时，成本如何放大通常比某台机器快多少更重要。

Big-O 是一个增长模型，不是计时器。不同机器会改变 constant factor， 但不会改变线性、二次、对数这些基本形状。

这个定义是一个 proof obligation。你要证明上界，而不是只说“看起来像 二次”。

化简规则不是偷懒，而是重点

tutorial slides 反复强调两条规则：

• 当 n 足够大时，删掉影响越来越小的项，
• 删掉 constant factor。

所以

0.1n^3 + 10000n^2 + n + 3

最后仍然是 $O(n^3)$。cubic term 会逐渐主导其他所有项。同样，

(n^2 + n)/2

的增长率仍然是 $O(n^2)$，因为 1/2 不会改变渐近形状。

CSCI2520 常见增长级别

课程里反复用到同一组 class。

• O(1)：直接访问、已知指针重连、简单算术。
• O(log n)：对半缩减搜索、平衡树查找、反复除 2。
• O(n)：扫描 array 或 linked list。
• O(n log n)：分治加上每一层的线性工作。
• $O(n^2)$：双重扫描，尤其是比较密集的 double loop。

for (int width = 1; width < n; width *= 2) {
  for (int i = 0; i < n; i += 2 * width) {
    merge_block(i, width);
  }
}

这个 comparator widget 只是视觉辅助，不是 derivation 的替代品。你应该先 写出增长式，再用 widget 去确认直觉。

从程序读出复杂度

最快的方法，通常是找出最常执行的部分，再数它跑了多少次。

int x = a + b;
int y = x * 2;
return y;

int sum(const int a[], int n) {
   int total = 0;
   for (int i = 0; i < n; i++) {
      total += a[i];
   }
   return total;
}

int countPairs(int n) {
   int c = 0;
   for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
         c++;
      }
   }
   return c;
}

一个具体排序例子：selection sort

tutorial deck 用 selection sort 去示范 quadratic growth 怎么出现。算法会在 剩余 suffix 里面找最小元素，再 swap 到正确位置。

void selectionSort(int a[], int n) {
   for (int i = 0; i < n - 1; i++) {
      int min = i;
      for (int j = i + 1; j < n; j++) {
         if (a[j] < a[min]) {
            min = j;
         }
      }
      if (min != i) {
         int tmp = a[i];
         a[i] = a[min];
         a[min] = tmp;
      }
   }
}

比较次数大约是

(n-1) + (n-2) + ... + 1 = n(n-1)/2.

这个和是二次，所以算法是 $O(n^2)$。slide 里用文字讲的重点也一样： 当 n 加倍，时间大约变成 4 倍。

comparison sort 与 non-comparison sort

sorting slides 进一步指出：merge sort、heapsort 和 quicksort 都是 comparison sort。

对于 comparison sort，worst-case comparisons 有 Ω(n log n) 的 lower bound。也就是说，任何 comparison sort 都不能在 worst case 打破这个渐近 界限。

如果想快过这个 lower bound，就要避免把 comparison 当成主要机制。这正是 counting sort 和 radix sort 的意义。

• counting sort 在 key range k 可控时可以是 linear time。
• radix sort 会逐个 digit 做 stable subroutine sorting。
• counting sort 不是 in-place comparison sort。

实际重点不是“所有 sort 都一样”，而是数据域和操作模型会决定应该用什么 复杂度类别。

为什么 lower terms 和 constants 会消失

tutorial 的 simplification slide 里有很多类似：

$N + 1 = O(N)$

和

$N^3 + 1000N^2 + N = O(N^3)$.

原因是最快增长的项会主导长期增长。低阶项仍然存在，但当 n 足够大时， 它们就不再重要。

best case、worst case、average case

同一个算法，单靠一个复杂度标签未必足够。不同输入安排，可以让成本表现 完全不同。

• Best case：最有利输入下的成本；
• Worst case：最昂贵输入下的成本；
• Average case：在某个概率模型下的平均成本。

binary search 就是一个好例子。

int binarySearch(const int a[], int n, int target) {
   int left = 0, right = n - 1;
   while (left <= right) {
      int mid = (left + right) / 2;
      if (a[mid] == target) return mid;
      if (a[mid] < target) left = mid + 1;
      else right = mid - 1;
   }
   return -1;
}

所以你看到复杂度结论时，一定要问：这里说的是哪个 case？如果没有特别说， 通常默认是 worst case。

divide-and-conquer 与 n log n 形状

slide deck 提到 merge-sort 类结构，因为这正是 n log n 最典型的例子。

标准推理分两层：

• 每一层都处理线性数量的数据；
• 总层数大约是 log n。

所以总成本就会变成 n log n。

读 code 时的复杂度检查表

当你看到一段新 code，最稳妥的顺序是：

1. 找出哪个操作重复得最多；
2. 数清楚外层 loop、recursion，或者 traversal 会让它执行多少次；
3. 分开 constant work 和 size-dependent work；
4. 等计数写清楚之后再做化简。

如果跳过计数，最后通常只是在猜。好的 complexity analysis 是先慢慢读， 再做短而准确的分类。

constants 仍然怎样重要

渐近记号描述的是长期形状，但不代表 constants 永远不重要。当 n 还小， 一个简单的 $O(n^2)$ routine，实际表现仍然可能跑赢一个隐藏常数很大的 O(n log n) routine。

所以比较完整的结论通常分两步：先把增长类别分清楚，再判断当前输入规模 是否仍然受到常数因素影响。

stack 和 queue 操作的成本

上一节 ADT 其实正好给这一节提供了具体例子。一旦 representation 固定， 同一个 interface 仍然可以有不同成本。

• array-based stack push / pop 通常是 constant time，但 resize 时会更贵。
• linked-list queue 如果 head 和 tail 维护得好，enqueue / dequeue 可以是 constant time。
• QueueLength() 如果要扫描 linked list，就可能是 linear time；如果有 length 字段，就可以是 constant time。

所以渐近分析一定要和实现细节一起看，不能分开。

重点总结

复杂度分析是用来理解 scaling 的，而不是猜哪个 implementation “感觉上更 快”。如果你能找出主导重复动作、写出计数、再正确化简，通常就可以不跑 程序也把算法分类出来。