时间复杂度的分析基础

思维导图

graph LR A[函数的增长] --> B[渐近符号体系] A --> C[时间复杂度分析] A --> D[递归算法复杂度计算] A --> E[应用举例] B --> B1[定义与用途] B1 --> B11["分析算法效率的数学工具"] B --> B2[符号分类] B2 --> B21["O (上界): ∃c,n₀>0, ∀n≥n₀, 0 ≤ f(n) ≤ cg(n)"] B2 --> B22["Ω (下界): ∃c,n₀>0, ∀n≥n₀, 0 ≤ cg(n) ≤ f(n)"] B2 --> B23["Θ (紧确界): 同时满足O和Ω"] B2 --> B24["o (非紧上界): limₙ→∞ f(n)/g(n)=0"] B2 --> B25["ω (非紧下界): limₙ→∞ f(n)/g(n)=∞"] C --> C1[分析原则] C1 --> C11["关注输入规模n→∞时的行为"] C1 --> C12["忽略低阶项与常数系数"] C --> C2[增长率比较] C2 --> C21["1 ≺ log n ≺ n ≺ n log n ≺ n² ≺ 2ⁿ"]

渐近符号体系

1. 核心符号定义

符号	数学定义	直观含义	典型用例
O (上界)	∃c,n₀>0，∀n≥n₀，0 ≤ f(n) ≤ c·g(n)	算法的最坏时间复杂度	插入排序最坏情况 O(n²)
Ω (下界)	∃c,n₀>0，∀n≥n₀，0 ≤ c·g(n) ≤ f(n)	算法的最低性能保证	比较排序下限 Ω(n logn)
Θ (紧确界)	同时满足 O(g(n)) 和 Ω(g(n))	算法的精确时间范围	归并排序 Θ(n logn)
o (非紧上界)	limₙ→∞ f(n)/g(n) = 0	严格弱于上界	2n = o(n²)
ω (非紧下界)	limₙ→∞ f(n)/g(n) = ∞	严格强于下界	n² = ω(n logn)

2. 符号关系

graph LR O --> Θ Ω --> Θ o --> O ω --> Ω

时间复杂度分析

1. 三大基本原则

忽略常数因子：硬件差异会掩盖常数影响
关注最高阶项：长期增长趋势由最高阶主导
考虑最坏情况：保证算法在任何输入下的性能下限

2. 常见函数增长率

1 \prec \log n \prec \sqrt{n} \prec n \prec n \log n \prec n^2 \prec 2^n

当 n=1,000,000 时

log2(n) ≈ 20      # 对数级
n = 1e6           # 线性级
n logn ≈ 20e6     # 线性对数级
n² = 1e12         # 平方级

xy0v0's Blog