第 2 章算法分析

Algorithm Analysis

为什么分析算法

同一个问题，可能有很多正确算法。算法分析关心的是：

输入规模变大时，运行时间如何增长
需要多少额外内存
最好、最坏、平均情况下差别有多大
哪些代码结构决定了主要成本
复杂度结论能否解释真实程序的性能变化

本章的目标不是“背 Big-O”，而是学会从代码和问题结构中推导成本。

本章路线图

算法分析
从代码到增长率

成本模型
时间与空间操作计数
找基本操作渐进符号
O / Ω / Θ 典型算法
查找与排序递归分析
分治与调用栈习题答案
循环求和

学习目标

完成本章后，应能回答：

性能分析和性能测量有什么区别
空间复杂度由哪些部分组成
如何选择基本操作并计算执行次数
如何分析顺序查找的最好、最坏和平均情况
为什么选择排序、冒泡排序、rank sort 的比较次数都是二次级
插入排序为什么最好线性、最坏二次
Big-O、Big-Ω、Big-Θ 分别表达什么
二分查找为什么是对数级
最大子段和问题如何从 \(O(n^3)\) 改进到 \(O(n^2)\) 和 \(O(n\log n)\)
欧几里得算法为什么是对数级

性能分析与性能测量

确定算法成本有两种互补方法：

性能分析：在运行前，根据代码和数学模型推导时间、空间复杂度
性能测量：实际运行程序，记录时间、内存、缓存、分支预测等表现

性能分析给出增长趋势。
性能测量反映具体机器、编译器、输入分布和实现细节。

课程中先学习分析，因为它能解释“为什么规模一大，某些程序突然不可用”。

工程连接：开源库为什么重视复杂度

复杂度分析会直接影响工程库的接口和实现选择。

C++ STL std::sort 使用 introsort 避免快速排序最坏退化

Python Timsort 利用已有有序片段降低实际成本

PostgreSQL 查询优化器估算排序、连接和扫描代价

Linux 调度和内存管理需要可预期的最坏成本

算法分析给出增长趋势，工程测量再检查 cache、分支预测、内存分配和输入分布带来的常数差异。

时间与空间

程序总时间可以粗略写成：

\[ T(p)=T_{\text{compile}}+T_{\text{run}} \]

编译时间通常不依赖本次输入规模；算法分析主要关心运行时间随实例特征变化的规律。

空间复杂度关注程序运行到结束所需内存。它同样随输入规模变化。

空间复杂度的组成

空间可以分成三类：

指令空间：程序代码本身
数据空间：常量、简单变量、数组、对象、动态分配空间
环境栈空间：保存尚未完成的函数调用信息

更常用的分析方式：

固定部分：与输入规模无关
可变部分：数组、动态空间、递归调用栈等随规模变化的空间

空间例子：顺序查找

int sequentialSearch(const std::vector<int>& a, int x) {
  for (int i = 0; i < static_cast<int>(a.size()); ++i) {
    if (a[i] == x) return i;
  }
  return -1;
}

除了输入数组本身，辅助变量只有 i、x 和常数个临时值。

因此辅助空间为：

\[ S_{\text{aux}}(n)=\Theta(1) \]

空间例子：递归求和

float recursiveSum(const std::vector<float>& a, int n) {
  if (n == 0) return 0.0f;
  return recursiveSum(a, n - 1) + a[n - 1];
}

递归深度是 \(n+1\)。每一层调用都需要保存参数、返回地址和局部状态。

如果每层栈帧占常数空间，则：

\[ S_{\text{stack}}(n)=\Theta(n) \]

时间复杂度：基本操作计数

时间分析通常分三步：

选择一个能代表主要成本的基本操作
数出它随输入规模执行多少次
用渐进符号表达增长阶

基本操作可以是：

比较
交换
数组访问
哈希计算
指针跳转
递归调用

选择哪个操作，取决于算法的核心成本在哪里。

例子：求最大元素位置

int maxPosition(const std::vector<int>& a) {
  int pos = 0;
  for (int i = 1; i < static_cast<int>(a.size()); ++i) {
    if (a[pos] < a[i]) {
      pos = i;
    }
  }
  return pos;
}

关键操作是比较 a[pos] < a[i]。

对长度为 \(n\) 的数组，它执行：\(n-1\) 次。因此时间复杂度为 \(\Theta(n)\)。

循环计数：三角形面积

选择排序：代码

选择排序每一轮在未排序区间中找到最小元素，再放到当前左端。

void selectionSort(std::vector<int>& a) {
  const int n = static_cast<int>(a.size());
  for (int i = 0; i < n - 1; ++i) {
    int k = i;
    for (int j = i + 1; j < n; ++j) {
      if (a[j] < a[k]) {
        k = j;
      }
    }
    std::swap(a[i], a[k]);
  }
}

选择排序：操作次数

第 \(i\) 轮内层比较次数是 \(n-i-1\)。

总比较次数：

\[ (n-1)+(n-2)+\cdots+2+1=\frac{n(n-1)}{2} \]

交换次数最多 \(n-1\) 次。若按三次赋值实现一次交换，元素移动次数约为 \(3(n-1)\)。

结论：

比较次数：\(\Theta(n^2)\)
移动次数：\(\Theta(n)\)
总时间：\(\Theta(n^2)\)

冒泡排序：一次冒泡

void bubblePass(std::vector<int>& a, int n) {
  for (int i = 0; i < n - 1; ++i) {
    if (a[i] > a[i + 1]) {
      std::swap(a[i], a[i + 1]);
    }
  }
}

一次冒泡会把当前区间中的最大元素推到最右端。
如果外层调用 bubblePass(a, i)，其中 \(i\) 从 \(n\) 递减到 \(2\)，比较次数仍是：

\[ \frac{n(n-1)}{2} \]

Rank Sort：用排名排序

Rank sort 先计算每个元素的排名，再根据排名重排数组。

void rankElements(const std::vector<int>& a, std::vector<int>& r) {
  const int n = static_cast<int>(a.size());
  std::fill(r.begin(), r.end(), 0);
  for (int i = 1; i < n; ++i) {
    for (int j = 0; j < i; ++j) {
      if (a[j] <= a[i]) ++r[i];
      else ++r[j];
    }
  }
}

每一对元素正好比较一次，因此比较次数也是：

\[ \frac{n(n-1)}{2} \]

Rank Sort：重排

如果排名数组 r[i] 表示 a[i] 应该去的位置，可以通过交换把元素放到正确位置。

void rearrange(std::vector<int>& a, std::vector<int>& r) {
  const int n = static_cast<int>(a.size());
  for (int i = 0; i < n; ++i) {
    while (r[i] != i) {
      int t = r[i];
      std::swap(a[i], a[t]);
      std::swap(r[i], r[t]);
    }
  }
}

比较阶段是 \(\Theta(n^2)\)，重排阶段是线性级别，因此总时间仍由比较阶段主导。

最好、最坏与平均

同一段代码在不同输入上可能成本不同。

最好情况：最有利输入
最坏情况：最不利输入
平均情况：按某种输入分布求期望

平均情况通常最难，因为它要求明确“输入如何随机产生”。
课程初期常先分析最好和最坏，再在必要时讨论平均。

顺序查找：最好、最坏、平均

int sequentialSearch(const std::vector<int>& a, int x) {
  for (int i = 0; i < static_cast<int>(a.size()); ++i) {
    if (a[i] == x) return i;
  }
  return -1;
}

若查找成功：

最好：目标在第 1 个位置，比较 1 次
最坏：目标在第 \(n\) 个位置，比较 \(n\) 次
平均：每个位置等概率，比较次数为:

\[ \frac{1+2+\cdots+n}{n}=\frac{n+1}{2} \]

插入排序：代码

插入排序维护一个已排序前缀，把新元素插入到正确位置。

void insertionSort(std::vector<int>& a) {
  const int n = static_cast<int>(a.size());
  for (int i = 1; i < n; ++i) {
    int t = a[i];
    int j = i - 1;
    while (j >= 0 && t < a[j]) {
      a[j + 1] = a[j];
      --j;
    }
    a[j + 1] = t;
  }
}

插入排序：最好与最坏

最好情况：数组已经有序。
每轮只比较一次，不移动元素：

\[ T_{\text{best}}(n)=\Theta(n) \]

最坏情况：数组逆序。
第 \(i\) 轮要移动 \(i\) 个元素：

\[ 1+2+\cdots+(n-1)=\frac{n(n-1)}{2} \]

因此：

\[ T_{\text{worst}}(n)=\Theta(n^2) \]

Step Counts：给每行计步

有时需要不只数关键操作，而是给所有语句计步。

int sum(const std::vector<int>& a) {
  int total = 0;                       // 1
  for (int i = 0; i < a.size(); ++i) { // n+1 次条件检查
    total += a[i];                     // n
  }
  return total;                        // 1
}

精确计步会得到类似 \(2n+3\) 的表达式。
渐进分析中，它与 \(n\) 属于同一增长阶：\(\Theta(n)\)。

渐进符号

渐进符号描述 \(n\) 很大时函数增长的主导趋势。

\(O(g(n))\)：上界，不超过某个常数倍的 \(g(n)\)
\(\Omega(g(n))\)：下界，至少达到某个常数倍的 \(g(n)\)
\(\Theta(g(n))\)：紧确界，上下界都是同一个增长阶

它们忽略常数因子和低阶项，但不忽略增长阶。

Big-O：上界

定义：

\[ f(n)=O(g(n)) \]

当且仅当存在正常数 \(c\) 和 \(n_0\)，使得对所有 \(n\ge n_0\)：

\[ f(n)\le c g(n) \]

例如：

\[ 3n+2 \le 4n \quad (n\ge 2) \]

所以 \(3n+2=O(n)\)。

Big-Ω 与 Big-Θ

下界：

\[ f(n)=\Omega(g(n)) \]

表示 \(f(n)\) 至少像 \(g(n)\) 那样快地增长。

紧确界：

\[ f(n)=\Theta(g(n)) \]

表示同时存在常数 \(c_1,c_2,n_0\)，使得：

\[ c_1g(n)\le f(n)\le c_2g(n)\quad(n\ge n_0) \]

如果能说 \(\Theta\)，就比只说 \(O\) 更精确。

常见增长等级

二分查找：代码与区间同步

int binarySearch(const std::vector<int>& a, int x) {
  int low = 0;
  int high = static_cast<int>(a.size()) - 1;
  while (low <= high) {
    int mid = low + (high - low) / 2;
    if (a[mid] < x) {
      low = mid + 1;
    } else if (a[mid] > x) {
      high = mid - 1;
    } else {
      return mid;
    }
  }
  return -1;
}

每次循环把候选区间约减半，因此最坏时间为 \(\Theta(\log n)\)。

最大子段和问题

给定整数序列 \(a_1,a_2,\ldots,a_n\)，允许存在负数，求连续子段的最大和：

\[ \max_{1\le i\le j\le n}\sum_{k=i}^{j}a_k \]

如果所有数均为负数，这里采用约定：最大子段和为 0。

例子：

\[ [-2,\ 11,\ -4,\ 13,\ -5,\ -2] \]

最大子段是 \([11,-4,13]\)，和为 20。

最大子段和：三种思路

算法 1：三层枚举

int maxSubSum1(const std::vector<int>& a) {
  int maxSum = 0;
  const int n = static_cast<int>(a.size());
  for (int i = 0; i < n; ++i) {
    for (int j = i; j < n; ++j) {
      int thisSum = 0;
      for (int k = i; k <= j; ++k) {
        thisSum += a[k];
      }
      maxSum = std::max(maxSum, thisSum);
    }
  }
  return maxSum;
}

枚举起点、终点、再求和，复杂度为 \(O(n^3)\)。

算法 2：固定起点向右累加

int maxSubSum2(const std::vector<int>& a) {
  int maxSum = 0;
  const int n = static_cast<int>(a.size());
  for (int i = 0; i < n; ++i) {
    int thisSum = 0;
    for (int j = i; j < n; ++j) {
      thisSum += a[j];
      maxSum = std::max(maxSum, thisSum);
    }
  }
  return maxSum;
}

对每个起点，向右扩展时复用前一次的和。
复杂度降为 \(O(n^2)\)。

算法 3：分治

把数组分成左右两半。最大子段只可能在三类位置：

完全在左半边
完全在右半边
跨过中点

递归求左右两边，再用线性扫描求跨中点最大和：

\[ T(n)=2T(n/2)+O(n) \]

因此：

\[ T(n)=O(n\log n) \]

分治代码：核心结构

int maxSumRec(const std::vector<int>& a, int left, int right) {
  if (left == right) return std::max(0, a[left]);

  int center = left + (right - left) / 2;
  int maxLeft = maxSumRec(a, left, center);
  int maxRight = maxSumRec(a, center + 1, right);

  int leftBorder = 0, bestLeftBorder = 0;
  for (int i = center; i >= left; --i) {
    leftBorder += a[i];
    bestLeftBorder = std::max(bestLeftBorder, leftBorder);
  }

分治代码：合并

  int rightBorder = 0, bestRightBorder = 0;
  for (int i = center + 1; i <= right; ++i) {
    rightBorder += a[i];
    bestRightBorder = std::max(bestRightBorder, rightBorder);
  }

  return std::max({maxLeft, maxRight,
                   bestLeftBorder + bestRightBorder});
}

int maxSubSum3(const std::vector<int>& a) {
  if (a.empty()) return 0;
  return maxSumRec(a, 0, static_cast<int>(a.size()) - 1);
}

欧几里得算法

欧几里得代码

long long gcd(long long m, long long n) {
  while (n != 0) {
    long long rem = m % n;
    m = n;
    n = rem;
  }
  return m;
}

核心不变量：

\[ \gcd(m,n)=\gcd(n,m\bmod n) \]

由于数字规模快速缩小，复杂度为 \(O(\log N)\)。

多维度分析表

算法	时间	空间	最好/最坏差异	关键原因
顺序查找	\(\Theta(n)\)	\(\Theta(1)\)	有	命中位置不同
二分查找	\(\Theta(\log n)\)	\(\Theta(1)\)	有	每步减半
选择排序	\(\Theta(n^2)\)	\(\Theta(1)\)	小	总要找最小值
插入排序	\(\Theta(n)\) 到 \(\Theta(n^2)\)	\(\Theta(1)\)	大	输入越有序越快
最大子段和分治	\(O(n\log n)\)	\(O(\log n)\)	小	每层线性合并
欧几里得	\(O(\log N)\)	\(\Theta(1)\)	有	余数快速缩小

分析算法的固定流程

遇到一段新代码，可以按这个顺序分析：

确定输入规模 \(n\) 或其他实例特征
选择关键操作
写出执行次数表达式
化简求和或递推式
用 \(O\)、\(\Omega\)、\(\Theta\) 表达增长阶
检查最好、最坏、平均是否不同
检查额外空间和递归栈

习题 1：selectkth

题目：分析在无序数组中找第 \(k\) 小元素的函数。

int selectKth(std::vector<int>& a, int k) {
  for (int i = 0; i < k; ++i) {
    int mini = i;
    for (int j = i + 1; j < static_cast<int>(a.size()); ++j) {
      if (a[j] < a[mini]) mini = j;
    }
    std::swap(a[i], a[mini]);
  }
  return a[k - 1];
}

习题 1：答案

外层执行 \(k\) 次。第 \(i\) 次内层比较：\(n-i-1\)次。总比较次数：

\[ \sum_{i=0}^{k-1}(n-i-1) =k(n-1)-\frac{k(k-1)}{2} \]

因此：

若 \(k\) 是常数：\(\Theta(n)\)
若 \(k\) 与 \(n\) 同阶：\(\Theta(n^2)\)
一般可写作：\(\Theta(kn-k^2)\)，常用上界 \(O(kn)\)

习题 2：两个对数循环

题目 c：

for (int i = 1; i <= n; i *= 2)
  for (int j = 1; j <= n; ++j)
    ++cnt;

外层执行 \(\lfloor\log_2 n\rfloor+1\) 次，内层每次 \(n\) 次。

\[ T(n)=\Theta(n\log n) \]

题目 d：

for (int i = 1; i <= n; i *= 2)
  for (int j = 1; j <= i; ++j)
    ++cnt;

总次数：

\[ 1+2+4+\cdots+2^{\lfloor\log_2 n\rfloor}<2n \]

所以 \(T(n)=\Theta(n)\)。

习题 3：三层循环一

sum = 0;
for (int i = 0; i < n; ++i)
  for (int j = 0; j < i * i; ++j)
    for (int k = 0; k < j; ++k)
      ++sum;

对固定 \(i\)：

\[ \sum_{j=0}^{i^2-1}j=\Theta(i^4) \]

总次数：

\[ \sum_{i=0}^{n-1}\Theta(i^4)=\Theta(n^5) \]

习题 3：三层循环二

sum = 0;
for (int i = 1; i < n; ++i)
  for (int j = 0; j < i * i; ++j)
    if (j % i == 0)
      for (int k = 0; k < j; ++k)
        ++sum;

只有 \(j=0,i,2i,\ldots,(i-1)i\) 时进入最内层。

对固定 \(i\)：

\[ \sum_{t=0}^{i-1}ti=i\frac{(i-1)i}{2}=\Theta(i^3) \]

总次数：

\[ \sum_{i=1}^{n-1}\Theta(i^3)=\Theta(n^4) \]

习题 4：矩阵乘法片段

for (int i = 1; i <= n; ++i)
  for (int j = 1; j <= n; ++j) {
    c[i][j] = 0.0;
    for (int k = 1; k <= n; ++k)
      c[i][j] = c[i][j] + a[i][k] * b[k][j];
  }

被分析语句在每个 \((i,j,k)\) 三元组上执行一次。

\[ T(n)=n\cdot n\cdot n=n^3 \]

所以复杂度为 \(\Theta(n^3)\)。

习题 4：嵌套求和片段

x = 0;
y = 0;
for (int i = 1; i <= n; ++i)
  for (int j = 1; j <= i; ++j)
    for (int k = 1; k <= j; ++k)
      x = x + y;

执行次数：

\[ \sum_{i=1}^{n}\sum_{j=1}^{i}\sum_{k=1}^{j}1 =\sum_{i=1}^{n}\sum_{j=1}^{i}j =\sum_{i=1}^{n}\frac{i(i+1)}{2} =\Theta(n^3) \]

习题 4：while 片段

int x = 91;
int y = 100;
while (y > 0) {
  if (x > 100) {
    x -= 10;
    --y;
  } else {
    ++x;
  }
}

从 x=91 到第一次 x>100，需要执行 10 次 else，使 x 变成 101。

之后每次减少 y 前：

若 x=101，执行一次 if 后变成 91
再执行 10 次 else 回到 101

因此循环次数为：

\[ 10+100\times 11=1110 \]

这是常数，与输入规模无关。

本章小结

本章的核心不是某个公式，而是一套分析习惯：

空间复杂度要看固定空间、输入空间、辅助空间和递归栈
时间复杂度先找关键操作，再数执行次数
嵌套循环通常转化为求和
递归和分治通常转化为递推式
\(O\) 是上界，\(\Omega\) 是下界，\(\Theta\) 是紧确界
同一个问题可以通过复用中间结果或改变结构显著降低复杂度

线性表、栈和队列会把这些分析方法落到具体结构上。

第 2 章 算法分析

为什么分析算法

本章路线图

学习目标

性能分析与性能测量

工程连接：开源库为什么重视复杂度

时间与空间

空间复杂度的组成

空间例子：顺序查找

空间例子：递归求和

时间复杂度：基本操作计数

例子：求最大元素位置

循环计数：三角形面积

选择排序：代码

选择排序：操作次数

冒泡排序：一次冒泡

Rank Sort：用排名排序

Rank Sort：重排

最好、最坏与平均

顺序查找：最好、最坏、平均

插入排序：代码

插入排序：最好与最坏

Step Counts：给每行计步

渐进符号

Big-O：上界

Big-Ω 与 Big-Θ

常见增长等级

二分查找：代码与区间同步

最大子段和问题

最大子段和：三种思路

算法 1：三层枚举

算法 2：固定起点向右累加

算法 3：分治

分治代码：核心结构

分治代码：合并

欧几里得算法

欧几里得代码

多维度分析表

分析算法的固定流程

习题 1：selectkth

习题 1：答案

习题 2：两个对数循环

习题 3：三层循环一

习题 3：三层循环二

习题 4：矩阵乘法片段

习题 4：嵌套求和片段

习题 4：while 片段

本章小结

第 2 章算法分析