1.4 算法复杂性分析
算法的渐进分析
- 数据规模 n 逐步增大时, f(n)的增长趋势
- 当 n 增大到一定值以后，计算公式中影响最大的就是 n 的幂次最高的项
- 其他的常数项和低幂次项都可以忽略
大O表示法
- 函数f，g定义域为自然数，值域非负实数集
- 定义: 如果存在正数c和n，使得对任意的 n > = n 0 n >=n_0 n>=n0，都有 f ( n ) ≤ c g ( n ) f(n)≤cg(n) f(n)≤cg(n)
- 称 f ( n ) f(n) f(n) 在集合 O ( g ( n ) ) O(g(n)) O(g(n)) 中，简称 f ( n ) 是 O ( g ( n ) ) f(n)是 O(g(n)) f(n)是O(g(n)) 的, 或 f ( n ) = O ( g ( n ) ) f(n)= O(g(n)) f(n)=O(g(n))
- 大 O 表示法: 表达函数增长率上限
- 一个函数增长率的上限可能不止一个
- 当上、下限相同时则可用 Θ 表示法(大O最常用, 大Θ也可简单看作大O)
大O表示法的单位时间
-
简单布尔或算术运算
-
简单 I/O
- 指函数的输入/输出
- 例如，从数组读数据等操作
- 不包括键盘文件等 I/O
-
函数返回
大 O 表示法的运算法则
-
加法规则: f 1 ( n ) + f 2 ( n ) = O ( m a x ( f 1 ( n ) , f 2 ( n ) ) ) f_1(n)+f_2(n)=O(max(f_1(n),f_2(n))) f1(n)+f2(n)=O(max(f1(n),f2(n)))
- 顺序结构，if 结构，switch 结构
-
乘法规则: f 1 ( n ) ⋅ f 2 ( n ) = O ( f 1 ( n ) ⋅ f 2 ( n ) ) f_1(n)·f_2(n) =O(f_1(n)·f₂(n)) f1(n)⋅f2(n)=O(f1(n)⋅f2(n))
- for, while, do-while 结构 (复杂度相乘)
- 例如：
for(i=0; i<n; i++) for (j=i; j<n; j++) k++;- 上述两个循环的复杂度为 n 2 = n ⋅ n n^2=n \cdot n n2=n⋅n
大Ω表示法
- 定义 :如果存在正数c和 no，使得对所有的 n ≥ n 0 n≥n_0 n≥n0都有 f ( n ) ≥ c g ( n ) f(n)≥ cg(n) f(n)≥cg(n), 则称 f(n) 在集合 Ω ( g ( n ) ) Ω(g(n)) Ω(g(n)) 中，或简称 f ( n ) f(n) f(n) 是 Ω ( g ( n ) ) Ω(g(n)) Ω(g(n)) 的，或 f ( n ) = Ω ( g ( n ) ) f(n)=Ω(g(n)) f(n)=Ω(g(n))
- 大 O表示法和大 Ω 表示法的唯一区别在于不等式的方向而已
- 采用大 Ω 表示法时，最好找出在函数增值率的所有下限中那个最"紧"(即最大)的下限
f ( n ) f(n) f(n)值越大, 复杂度增长率越高, 效率越低
时空权衡
- 增大空间开销可能改善算法的时间开销
- 可以节省空间，往往需要增大运算时间