算法分析深入
深入掌握大 O、大 Omega 和大 Theta 表示法,严谨地分析和比较算法效率。
你将学到
- 大 O、大 Omega、大 Theta 的形式化定义
- 如何从基本原理证明渐近界
- 常见复杂度类别及其增长率
- 操作序列的摊还分析
概念讲解
算法分析深入
渐近表示法为我们提供了一种描述算法资源使用量随输入增长而增长的语言。最重要的三种表示法是大 O(上界)、大 Omega(下界)和大 Theta(紧确界)。形式化地,f(n) = O(g(n)) 意味着存在正常数 c 和 n0,使得对所有 n >= n0,有 0 <= f(n) <= c*g(n)。
证明界
要证明 f(n) = O(g(n)),你需要找到常数 c 和 n0 并证明不等式成立。例如,要证明 3n^2 + 5n + 7 = O(n^2),取 c = 15 和 n0 = 1:对 n >= 1,3n^2 + 5n + 7 <= 15n^2。技巧在于选择足够大的 n0,使低阶项被主导。
复杂度类别层次
从最慢到最快:O(1) < O(log n) < O(sqrt(n)) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)。O(n log n) 算法在大输入上比 O(n^2) 快得多。
摊还分析
某些操作偶尔昂贵但平均廉价。动态数组的追加操作是 O(1) 摊还的,即使扩容是 O(n)——因为扩容很少发生。聚合方法将所有成本求和并除以 n。
示例代码
// Proving 3n^2 + 5n + 7 = O(n^2) empirically
function f(n) { return 3*n*n + 5*n + 7; }
function g(n) { return n*n; }
let c = 15, n0 = 1, holds = true;
for (let n = n0; n <= 100000; n++) {
if (f(n) > c * g(n)) { holds = false; break; }
}
console.log(`Bound holds: ${holds}`);
// Amortized: dynamic array append
class DynamicArray {
constructor() { this.arr = new Array(1); this.size = 0; }
append(x) {
if (this.size === this.arr.length) {
const newArr = new Array(this.arr.length * 2);
for (let i = 0; i < this.size; i++) newArr[i] = this.arr[i];
this.arr = newArr;
}
this.arr[this.size++] = x;
}
}
const da = new DynamicArray();
for (let i = 0; i < 100; i++) da.append(i);
console.log('Capacity:', da.arr.length, 'Size:', da.size);
第一部分经验性地验证大 O 界。DynamicArray 展示了摊还 O(1) 追加——扩容使容量翻倍,因此每个元素在每个翻倍周期最多被复制一次。
动手试一试
- Code Diff
比较两种算法实现,观察复杂度如何影响实际性能。
常见错误
错误写法
混淆大 O(上界)和大 Theta(紧确界)。
正确做法
大 O 只表示不会比...差。O(n) 算法也是 O(n^2)。当你指恰好此增长率时使用大 Theta。
错误写法
在摊还分析中忽略常数。
正确做法
摊还 O(1) 意味着 n 次操作的总成本是 O(n),而非每次操作都是 O(1)。
查阅不认识的术语
新手友好的术语表用大白话解释编程术语——变量、函数、DOM、Promise 等等。
动手做项目
通过引导式项目应用所学,含起始代码与解决方案。
解读错误信息
用大白话解释常见错误——什么意思、为什么发生、如何修复。