时间复杂度的分析基础
思维导图
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 # 平方级