xy0v0's Blog

Back

思维导图#

渐近符号体系#

1. 核心符号定义#

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

2. 符号关系#

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

时间复杂度分析#

1. 三大基本原则#

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

2. 常见函数增长率#

1≺log⁡n≺n≺n≺nlog⁡n≺n2≺2n1 \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         # 平方级
python

时间复杂度的分析基础

https://www.xy0v0.top/blog/1739192468
Author xy0v0 Published at Copyright CC BY-NC-SA 4.0