第 2 章 算法分析

Algorithm Analysis

算法分析引入

假设有两个程序都能正确完成同一个任务。

输入只有 100 个元素时：

• 程序 A：0.2 ms
• 程序 B：0.3 ms

几乎没有区别。

但如果 A 的工作量大约随 \(n^2\) 增长，而 B 大约随 \(n\log n\) 增长，当输入扩大到 100 万时，两者可能从“都很快”变成“一个还能运行，另一个几乎不可用”。

在真正运行大规模输入之前，能不能从代码结构本身预测这种差距？

规模放大会暴露很多不同的成本问题

• 查找：顺序查找（sequential search）和二分查找（binary search）在小数组上都很快，规模扩大后差距明显
• 排序：二次增长与“接近线性但多一个对数因子”的增长，在数据量上升时会进入完全不同的区间
• Transformer 注意力机制：序列长度增大时，标准自注意力的计算和显存成本会快速增长
• 智能体工作流：搜索分支数和最大深度增加时，工具调用与模型调用的总成本可能迅速放大

因此算法分析要建立一套不依赖某台机器、能够解释规模变化的成本模型（cost model）。

本章将从时间与空间、基本操作（basic operation）计数、最好情况（best case）/最坏情况（worst case）/平均情况（average case）出发，再用渐进记号（asymptotic notation）把具体计数提升为可比较的增长率。

本章路线图

算法分析
从代码到增长率

成本模型
时间与空间 操作计数
找基本操作 渐进符号
O / Ω / Θ 典型算法
查找与排序 递归分析
分治（divide and conquer）与调用栈

学习目标

完成本章后，应能回答：

• 性能分析和性能测量有什么区别
• 空间复杂度（space complexity）由哪些部分组成
• 如何选择基本操作并计算执行次数
• 如何分析顺序查找的最好、最坏和平均情况
• 为什么选择排序（selection sort）、冒泡排序（bubble sort）、排名排序（rank sort）的比较次数都是二次级
• 插入排序（insertion sort）为什么最好线性、最坏二次
• \(O\)、\(\Omega\)、\(\Theta\) 三种渐进记号分别表达什么
• 二分查找为什么是对数级
• 最大子段和问题如何从三次增长改进到二次增长，再改进到“线性 × 对数”增长
• 辗转相除法为什么是对数级

成本模型

性能分析与性能测量

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

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

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

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

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

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

Java 标准库 Java Arrays.sort / Collections.sort 的库实现会用工程化策略避免朴素快速排序（quicksort）的常见退化

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

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

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

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

时间与空间

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

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

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

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

空间复杂度的组成

空间可以分成三类：

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

更常用的分析方式：

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

空间例子：顺序查找

static int sequentialSearch(int[] a, int x) {
    for (int i = 0; i < a.length; i++) {
        if (a[i] == x) {
            return i;
        }
    }
    return -1;
}

sequentialSearch(…) 从左到右寻找目标并返回命中位置；在命中前，已扫描前缀都可确定不含目标。

扫描只维护当前位置 i；候选逐个被排除，不需要随数组长度增长的辅助存储。

一旦命中就立即结束，后续位置不再可能改变“首次命中”的答案。

只有完整扫描仍未命中才返回 -1；除输入外始终只占常数个标量，因此辅助空间是常数级，不会随数组长度增长。

空间例子：递归求和

static float recursiveSum(float[] a, int n) {
    if (n < 0 || n > a.length) {
        throw new IllegalArgumentException("n out of range");
    }
    if (n == 0) {
        return 0.0f;
    }
    return recursiveSum(a, n - 1) + a[n - 1];
}

recursiveSum(…) 返回给定前缀的总和；递归每层只负责把一个元素并入更小前缀的结果。

n 是当前前缀长度；先限制到合法范围，递归规模才不会越过数组边界。

空前缀返回 0，为递归提供停止点，也给逐层相加提供不会改变结果的单位元。

每层只缩短一个元素，却要保留一层未完成调用；深度随 n 同步增长，所以递归栈空间是线性增长。

操作计数

时间复杂度（time complexity）：基本操作计数

时间分析通常分三步：

1. 选择一个能代表主要成本的基本操作
2. 数出它随输入规模执行多少次
3. 用精确次数或自然语言描述它随输入规模的增长趋势

基本操作可以是：

• 基本运算
  • 四则运算
  • 比较
  • 布尔运算
• 内存读写
  • 数组访问
  • 指针解引用
• 程序计数器跳转
  • 函数调用
  • 分支/循环

求最大元素位置

问题描述

给定一个非空数组，返回其中最大元素所在的下标。

例如输入 [8, 25, 16, 30]，答案应为下标 3。

思路分析

维护一个变量 pos，表示“到目前为止见过的最大元素位置”。从左向右扫描，每遇到更大的元素就更新 pos。

关键操作是比较 a[pos] < a[i]。长度为 \(n\) 时恰好比较 \(n-1\) 次，因此是线性增长。

求最大元素位置

求最大元素位置

static int maxPosition(int[] a) {
    if (a.length == 0) {
        throw new IllegalArgumentException("a must not be empty");
    }
    int max = 0;
    for (int i = 1; i < a.length; i++) {
        if (a[i] > a[max]) {
            max = i;
        }
    }
    return max;
}

maxPosition(…) 返回最大元素的位置而不是值；扫描过程中只维护当前最佳下标。

空数组没有最大元素，先拒绝它，后面才能安全把第 0 个元素作为比较基准。

max=0 建立不变量：max 始终指向已扫描前缀中的最大元素；因此扫描从位置 1 开始。

新元素更大时才更新 max；每轮结束后，“前缀最大值位置”这一不变量仍然成立。

扫描完全部 n-1 个新候选后，前缀就是整个数组，因此 max 是全局最大值位置；比较次数随 n 线性增长。

基本/不基本运算的判断

有些运算并不基本。最突出的例子是哈希函数的计算。

• 在输入不定长、没有上界时，哈希函数本身的开销也没有上界
• 只有输入长度固定时，哈希计算可以被认为是一个基本运算

基本运算的有限组合都可以看做一次基本运算。例如：

• 交换两个变量/内存位置
• 进行一次函数调用，这个函数内部没有循环也没有任何函数调用

选择排序

思路分析

把数组分成“已排序前缀”和“未排序区间”。每一轮扫描未排序区间，记录最小元素的位置，扫描结束后与当前左端交换。

核心不变量是：第 \(i\) 轮结束后，前 \(i+1\) 个位置已经是全局最小的 \(i+1\) 个元素，并且以后不会再改变。

选择排序代码

static void selectionSort(int[] a) {
    for (int i = 0; i + 1 < a.length; i++) {
        int min = i;
        for (int j = i + 1; j < a.length; j++) {
            if (a[j] < a[min]) {
                min = j;
            }
        }
        int tmp = a[i];
        a[i] = a[min];
        a[min] = tmp;
    }
}

selectionSort(…) 每轮把未排序区的最小元素放到边界位置，并逐步扩大已确认有序前缀。

位置 i 是本轮要永久确定的位置；进入这一轮时，前缀 [0,i) 已经是全局最小的一批元素。

min 从未排序区间左端起步，内层扫描只负责回答一个问题：这一轮真正的最小值在哪里。

发现更小候选就更新 min；扫描结束时它指向整个未排序区间的最小元素。

交换把该最小值放到 i，于是已排序前缀增长一格；比较总数累加为 n(n-1)/2。

选择排序：操作次数

第 \(i\) 轮比较 \(n-i-1\) 次，因此总比较次数是 \((n-1)+(n-2)+\cdots+1=\frac{n(n-1)}{2}\)。

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

结论：

• 比较：二次增长 —— 主导项是 \(n^2\)
• 移动：线性增长 —— 最多与 \(n\) 成正比
• 因而总运行成本由比较主导，表现为二次增长

冒泡排序

思路分析

从左到右比较相邻元素。如果左边比右边大，就交换它们。较大的元素会像“气泡”一样不断向右移动。

一轮结束后最右端元素已经就位；下一轮可以忽略它，只处理更短的前缀。

冒泡排序代码

static void bubblePass(int[] a, int n) {
    if (n < 0 || n > a.length) {
        throw new IllegalArgumentException("n out of range");
    }
    for (int i = 1; i < n; i++) {
        if (a[i - 1] > a[i]) {
            int tmp = a[i - 1];
            a[i - 1] = a[i];
            a[i] = tmp;
        }
    }
}

bubblePass(…) 完成一趟相邻比较，把当前最大元素推到本趟末端。

n 定义本轮仍需处理的前缀；先校验边界，才能安全把 n-1 当作本轮最终位置。

从左到右检查相邻对，只有逆序才交换；较大的值因此会被一次次推向右侧。

三次赋值共同完成一次交换；整轮结束后，活动前缀的最大值必然到达 n-1，下一轮可永久忽略它。

情况分析

最好、最坏与平均

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

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

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

顺序查找

问题描述

给定一个数组和目标值 x，返回 x 第一次出现的位置；如果不存在，返回 -1。

数组不要求有序，因此不能依赖大小关系跳过一整段位置。

思路分析

从左到右逐个比较 a[i] 和 x。一旦相等立即返回当前位置；扫描到末尾仍未命中则返回 -1。

这个算法的成本直接由“目标出现在第几个位置”决定。

顺序查找

顺序查找代码

static int sequentialSearch(int[] a, int x) {
    for (int i = 0; i < a.length; i++) {
        if (a[i] == x) {
            return i;
        }
    }
    return -1;
}

sequentialSearch(…) 从左到右寻找目标并返回命中位置；在命中前，已扫描前缀都可确定不含目标。

每检查一个位置只做一次关键比较；因此成本直接等于“目标第一次出现之前要走过多少候选”。

若第一个位置就命中，只需 1 次比较；命中后立即返回使最好情况保持常数成本。

若目标在末尾或根本不存在，所有 n 个位置都必须检查，因此最坏情况的比较次数随 n 线性增长。

若成功位置等概率，比较次数在 1..n 上均匀分布，平均为 (n+1)/2，仍是线性增长。

插入排序

问题描述

给定一个无序数组，把它按从小到大排列。

思路分析

维护一个已排序前缀。取出下一个元素 t，把所有比 t 大的前缀元素向右移动一格，再把 t 放进留下的空位。

核心不变量是：每轮结束后，前缀始终保持有序。

插入排序代码

static void insertionSort(int[] a) {
    for (int p = 1; p < a.length; p++) {
        int tmp = a[p];
        int j = p;
        while (j > 0 && tmp < a[j - 1]) {
            a[j] = a[j - 1];
            j--;
        }
        a[j] = tmp;
    }
}

insertionSort(…) 逐个扩展有序前缀；每次把新元素插入它在前缀中的正确位置。

进入第 p 轮时，前缀 [0,p) 已经有序；本轮只需把一个新元素插进去。

tmp 暂存待插入值，j 表示当前“空位”；这样移动前缀元素时不会丢掉待插入值。

只要左邻居更大，就把它右移并让空位左移；有序前缀因此无需整体重排，只为 tmp 腾位置。

把 tmp 放入最终空位后，新前缀仍有序；已排序输入几乎不移动，逆序输入则产生二次移动。

插入排序：最好与最坏

最好情况：数组已经有序。
每轮只比较一次，不移动元素；总比较次数与 \(n\) 成正比，因此是线性增长。

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

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

因此最坏情况下，移动次数的主导项与 \(n^2\) 成正比，属于二次增长。

逐行计步：给每行计算执行次数

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

static int sum(int[] a) {
    int total = 0;
    for (int value : a) {
        total += value;
    }
    return total;
}

sum(…) 返回这段循环结构产生的累计结果/执行次数，用来把代码行为转成可计算的复杂度表达式。

total=0 选用加法单位元建立累计不变量：处理过的前缀之和始终保存在 total 中。

每个元素恰好进入累计值一次；随 n 增长，真正重复的工作正是这一轮更新。

循环结束后累计值就是全数组之和；无论精确计步写成 2n+3 还是别的常数形式，主导项都与 n 成正比，因此是线性增长。

渐进增长

渐进符号

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

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

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

\(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)\)。

\(\Omega\) 与 \(\Theta\) 记号

下界：

\[ 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\) 更精确。

常见增长等级

对数算法

二分查找

问题描述

给定一个已经按升序排列的数组和目标值 x，返回 x 所在的位置；如果不存在，返回 -1。

和顺序查找不同，这里可以利用“有序”这一额外条件一次排除大量候选位置。

思路分析

维护候选区间 [low, high]，每次检查中点 mid：

• a[mid] < x：目标只可能在右半边
• a[mid] > x：目标只可能在左半边
• a[mid] == x：直接返回

每轮候选区间大约减半，因此比较轮数是对数级。

二分查找

二分查找代码

static int binarySearchTraceable(int[] a, int x) {
    int left = 0;
    int right = a.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (a[mid] < x) {
            left = mid + 1;
        } else if (a[mid] > x) {
            right = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}

方法接收有序数组与目标值，并返回命中位置；后续所有判断都只缩小“仍可能包含目标”的候选区间。

[left,right] 初始覆盖整个有序数组；核心不变量是：目标若存在，就一定仍在这个候选区间内。

只要 left≤right，候选区间就还非空；当左右边界交错时，所有位置都已被排除。

只检查候选区间中点，就能借助有序性决定整半区的去留；安全写法同时避免下标相加溢出。

中点值 4 小于目标 6，因此中点及其左侧都不可能命中；这不是逐个排除，而是整段证明不可能。

把 left 推到 mid+1，只保留仍可能含有 6 的右半区，不变量继续成立。

新区间必须重新取中点；二分查找始终只围绕“当前仍可能的区间”继续判断。

中点值 8 大于 6，因此中点及右侧整体失去资格；有序性再次让一半候选一次消失。

把 right 收到 mid-1，候选集只留下仍可能等于 6 的左侧部分。

候选区间再次约减半；第三次取中点已经落到目标位置 5。

既不小于也不大于只能是相等；候选区间不再需要继续缩小，答案已经确定。

返回的是命中位置而不是值；调用者已知目标值，真正缺少的信息是它出现在哪里。

若区间最终缩空才返回 -1；每轮至少丢掉约一半候选，所以比较轮数为 O(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：三层枚举

思路分析

最直接的方法是枚举所有连续子段：第一层选择起点 i，第二层选择终点 j，第三层重新扫描 [i,j] 求和。

它几乎是问题定义的直接翻译，因此最容易验证正确性；代价是大量重复求和。

最大子段和算法1实现

static int maxSubSum1(int[] a) {
    int best = 0;
    for (int i = 0; i < a.length; i++) {
        for (int j = i; j < a.length; j++) {
            int thisSum = 0;
            for (int k = i; k <= j; k++) {
                thisSum += a[k];
            }
            best = Math.max(best, thisSum);
        }
    }
    return best;
}

maxSubSum1(…) 返回连续子段的最大和；不同实现只改变候选区间被枚举或合并的方式。

best=0 表示目前允许选择空子段；之后它始终保存已经检查过的区间中的最大和。

i 与 j 枚举所有连续区间的左右端点，因此候选区间本身已经有 Θ(n²) 个。

每确定一个 [i,j] 又从头扫描整段求和；大量区间共享元素却重复计算，这一层把成本推到 O(n³)。

每个区间求出和后只需与 best 比较；循环结束时所有连续区间都已被考虑。

返回最终最优值；这个实现正确但故意保留重复工作，为后面的增量求和提供改进对象。

最大子段和算法2：固定起点累加

思路分析

观察算法 1 的重复工作：当终点从 j 扩展到 j+1 时，前面的区间和已经算过，没有必要重新扫描。

因此固定起点 i 后，用 thisSum 从左到右累加；每扩展一个终点只做一次加法。

最大子段和算法2实现

static int maxSubSum2(int[] a) {
    int best = 0;
    for (int i = 0; i < a.length; i++) {
        int thisSum = 0;
        for (int j = i; j < a.length; j++) {
            thisSum += a[j];
            best = Math.max(best, thisSum);
        }
    }
    return best;
}

maxSubSum2(…) 返回连续子段的最大和；不同实现只改变候选区间被枚举或合并的方式。

best 仍保存已见区间的最优和；算法改进不改变答案不变量，只改变候选和的计算方式。

固定左端点 i 后把当前和清零；接下来所有候选都从同一个起点向右扩展。

右端点每前进一步只新增 a[j]，直接复用上一段的和；这正好删除了算法 1 的整段重复扫描。

对每个起点仍检查所有终点，所以候选数是 Θ(n²)；每个候选只做常数工作，整体降为 O(n²)。

全部起点和终点都处理后，best 已覆盖所有连续子段；返回它就是算法 2 的最终答案。

最大子段和算法3：分治

思路分析

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

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

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

从中点向左扫：只保留能贴着中点向左延伸的最大边界和。

从中点向右扫：同理得到右侧最大边界和；两者相加就是“跨中点”候选。

最终的时间复杂度：\(T(n)=2T(n/2)+O(n)\)

因此：\(T(n)=O(n\log n)\)

最大子段和算法3：分治

最大子段和算法3：分治实现

static int maxSubSumDivide(int[] a) {
    if (a.length == 0) {
        return 0;
    }
    return maxSumRec(a, 0, a.length - 1);
}

static int maxSumRec(int[] a, int left, int right) {
    if (left < 0 || right >= a.length || left > right) {
        throw new IllegalArgumentException("invalid subarray range");
    }
    if (left == right) {
        return Math.max(a[left], 0);
    }
    int center = left + (right - left) / 2;
    int maxLeftSum = maxSumRec(a, left, center);
    int maxRightSum = maxSumRec(a, center + 1, right);

    int maxLeftBorderSum = 0;
    int leftBorderSum = 0;
    for (int i = center; i >= left; i--) {
        leftBorderSum += a[i];
        maxLeftBorderSum = Math.max(maxLeftBorderSum, leftBorderSum);
    }

    int maxRightBorderSum = 0;
    int rightBorderSum = 0;
    for (int i = center + 1; i <= right; i++) {
        rightBorderSum += a[i];
        maxRightBorderSum = Math.max(maxRightBorderSum, rightBorderSum);
    }

    return Math.max(Math.max(maxLeftSum, maxRightSum), maxLeftBorderSum + maxRightBorderSum);
}

maxSubSumDivide(…) 返回连续子段的最大和；不同实现只改变候选区间被枚举或合并的方式。

外层只处理空数组约定，并把整个有效区间交给递归；分治逻辑集中在同一个区间问题上。

maxSumRec(…) 返回连续子段的最大和；不同实现只改变候选区间被枚举或合并的方式。

每个递归调用都代表一个合法闭区间；先检查边界，保证后面的切分和数组访问都有定义。

区间缩成一个元素时不能再分；答案就是该元素与空子段 0 中的较大者。

中点把候选分成“全在左边”和“全在右边”两类，递归直接求出这两个最优值。

跨中点子段若要最优，左半部分必须是“紧贴中点”的最大后缀；向左一次扫描即可求出。

右半同理只需“紧贴中点”的最大前缀；两侧相加就是所有跨中点候选中的最优值。

三类候选取最大即覆盖所有可能子段；每层额外扫描 O(n)，故 T(n)=2T(n/2)+O(n)=O(n log n)。

最大子段和：三种算法对照

• 明确输入与目标：允许负数，空子段和按 0 处理。
• 三层枚举：先选起点 i=1。
• 再选终点 j=3。
• 第三层重新求和，得到 11 + (-4) + 13 = 20。
• 改进一：固定 i 后向右累加，不再每次从头求和。
• 累加到 j=1：当前和为 11。
• 累加到 j=2：当前和为 7。
• 累加到 j=3：当前和为 20，刷新最好答案。
• 改进二：分治把数组分成左右两半。
• 最优子段可能完全在左半边。
• 也可能完全在右半边。
• 还可能跨过中点；本例最优跨中点。
• 三种思路比较：O(n³)、O(n²)、O(n log n)，还能继续优化到 O(n)。

Kadane算法：先只观察

从左到右看：每个前缀 \(0\ldots i\) 里，最大子段和是多少？

• 单独的负数前缀：舍弃。
• 一段累加到 \(<0\)：不要再接到后面。
• 最优子段里出现负数：至少一侧的和要能抵消它。

Kadane算法：把观察变成状态

endHere = max(0, endHere + a[i])
bestSoFar = max(bestSoFar, endHere)

一遍扫描：\(O(n)\) 时间，\(O(1)\) 空间。

辗转相除法（欧几里得算法）

问题描述

给定两个正整数 \(m\) 和 \(n\)，求它们的最大公因数 \(\gcd(m,n)\)。

直接枚举所有可能的公因数当然可以，但如果数很大，逐个尝试会非常慢。我们希望利用数本身的结构快速缩小问题规模。

例如：

\(\gcd(50,15)=5\)

关键问题是：怎样把 \((50,15)\) 转换成一个更小、但答案完全相同的问题？

辗转相除法

思路分析

设 \(g=\gcd(m,n)\)，则 \(m=k_mg,\ n=k_ng\)。

任意做整数次减法都有

\(m-qn=(k_m-qk_n)g\)

所以减法不会改变最大公约数。

连续减很多次可压缩成一次取余。设\(m>n\):

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

而且 \(0\le m\bmod n<n\)，因此每一步都会把数缩小，过程一定在余数变成 0 时结束。

辗转相除法

static int gcd(int m, int n) {
    if (m <= 0 || n <= 0) {
        throw new IllegalArgumentException("m and n must be positive");
    }
    while (n != 0) {
        int r = m % n;
        m = n;
        n = r;
    }
    return m;
}

方法要把两个正整数约化为一个最大公因数；整个循环只允许做不改变 gcd(m,n) 的状态变换。

这里采用正整数定义域；拒绝非正输入后，余数保持非负且严格小于除数，递减过程才有明确终点。

循环始终维持 gcd(m,n) 不变；只要 n≠0，就把问题改写成答案相同但规模更小的一对数。

50%15=5 给出下一轮唯一需要的新信息；由 gcd(m,n)=gcd(n,m%n)，丢掉商不会损失答案。

旧除数成为下一轮较大的参数；这不是普通赋值，而是在构造等价子问题 gcd(15,5)。

余数成为新的第二参数，并且严格小于旧 n；这个单调缩小保证过程最终会停。

余数变成 0，说明当前较小数已经整除较大数；此时不再存在更小的非零余数问题。

最后一次状态迁移把当前除数 5 保留下来；它就是所有前面等价问题共同的最大公因数。

n=0 使下一次循环检查失败；终止状态被规范成 (g,0) 的形式。

循环停止的数学理由是 gcd(g,0)=g；这正把“何时停”与“停下时为什么正确”连在一起。

返回当前 m 即得到原问题答案；全程只维护两个数和一个余数，辅助空间为常数级。

辗转相除法：复杂度分析

设 \(m\ge n>0\)。一轮把 \((m,n)\) 变成 \((n,\ m\bmod n)\)。

为什么规模会很快缩小？只需分两种情况：

• 若 \(n\le m/2\)，一轮后较大的参数已经不超过 \(m/2\)。
• 若 \(n>m/2\)，则 \(m\bmod n=m-n<m/2\)；再做一轮后，两个参数都会小于 \(m/2\)。

因此，至多两轮，较大的参数至少减半。每减半一次只需常数轮，所以迭代次数是

\(T(m,n)=O(\log \min(m,n))\)。

辗转相除法：确实会达到 \(\log n\)

连续 Fibonacci 数正好让余数下降得最慢。例如：

\((21,13)\rightarrow(13,8)\rightarrow(8,5)\rightarrow(5,3)\rightarrow(3,2)\rightarrow(2,1)\rightarrow(1,0)\)

每次只下降一个 Fibonacci 层级。一般地，输入 \((F_{k+1},F_k)\) 时需要约 \(k\) 次取模，而

\(F_k\approx \frac{\varphi^k}{\sqrt5}\)，因此 \(k=\Theta(\log F_k)\)。

所以辗转相除法确实需要 \(\Theta(\log n)\) 次迭代。

辗转相除法：时间和空间复杂度

前面的 \(\Theta(\log n)\) 只是取模次数，不是计算复杂度。m % n 不能算一个基本操作。

设输入长度是 \(L_m,L_n\)，且 \(L_m\ge L_n\)。

那么首次长整数取余的竖式计算步数为 \(L_m-L_n+1\)，每步的读写是 \(L_n\)，总共是

\[ O\bigl(L_n(L_m-L_n+1)\bigr), \]

关于输入长度是平方的。

只需要保留计算过程中的余数，辅助空间是 \(O(L_n)\)。

以上是一次迭代。多次迭代的结果是？

辗转相除法：时间和空间复杂度

设连续各个数的长度为 \(L_0=L_m, L_1=L_n, L_2,\ldots\)，且 \(L_0\ge L_1\ge L_2\ge\cdots\)。

第 \(i\) 次取余的时间为 \(O\bigl(L_{i+1}(L_i-L_{i+1}+1)\bigr)\)，所以总时间为 \(T=\sum_i O\bigl(L_{i+1}(L_i-L_{i+1}+1)\bigr)\)。

又因为每个后续数都不比 \(n\) 更长，即 \(L_{i+1}\le L_n\)，因此 \(T\le O\left(L_n\sum_i(L_i-L_{i+1}+1)\right)\)。

辗转相除法：时间和空间复杂度

\(T\le O\left(L_n\sum_i (L_i-L_{i+1}+1)\right).\)

其中长度差会折叠：\(\sum_i(L_i-L_{i+1})=L_m-L_{last}=O(L_m).\)

因此 \(T=O\bigl(L_n(L_m+L_n)\bigr).\)

由于 \(L_m\ge L_n\)，\(\boxed{T=O(L_mL_n)}.\)

再详细分析Fibonacci型输入，最坏情况下确实可以达到\(\boxed{\Theta(L^2)}.\)

辅助空间方面，迭代过程中只需要保存当前两个数和余数；若不计输入本身，辅助空间为\(\boxed{O(L_n)}.\)

本章小结

• 性能测量回答“这台机器上跑了多久”，性能分析回答“规模增长时成本怎样变化”。
• 空间复杂度要区分输入存储、固定变量、辅助数组以及递归调用栈。
• 基本操作应选取最能代表主导成本的语句，再用循环、嵌套和递归关系计算执行次数。
• 顺序查找的成本随目标位置变化，因此最好、最坏和平均情况必须分开讨论。
• 选择排序、冒泡排序和排名排序都包含成对比较或双层扫描，比较次数属于二次级。
• 插入排序利用已有有序性；输入接近有序时移动少，逆序时移动达到二次级。
• \(O\) 给上界，\(\Omega\) 给下界，\(\Theta\) 给紧确量级。
• 二分查找每一步丢弃一半候选区间，因此比较次数随区间长度按对数增长。
• 最大子段和可以通过消除重复求和、分治合并等方式，把朴素三次级逐步改进。
• 辗转相除法的取模迭代次数对数级增长；若把大整数取模本身的位运算成本算进去，最坏位复杂度需要单独分析，不能把一次 % 当作常数时间。

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

下载本章完整 Gradle 工程

本章习题

• 习题 1：选择第 \(k\) 小元素：题目：分析在无序数组中找第 \(k\) 小元素的函数。
• 习题 2：两个对数循环：分析题中两个含倍增外层循环的代码片段，分别求它们的执行次数和渐进时间复杂度。
• 习题 3：三层循环一：分析题中两个三层循环片段，分别计算最内层语句的执行次数，并给出渐进时间复杂度。
• 习题 4：矩阵乘法片段：分析题中三个代码片段（矩阵乘法式三重循环、嵌套求和、while 片段）的执行次数与时间复杂度。

致谢

谢谢

sqlite@nju.edu.cn
https://slab-nju.cn

石守谦