1.4 算法复杂性分析

算法的渐进分析

• 数据规模 n 逐步增大时, f(n)的增长趋势
• 当 n 增大到一定值以后，计算公式中影响最大的就是 n 的幂次最高的项
• 其他的常数项和低幂次项都可以忽略

大O表示法

• 函数f，g定义域为自然数，值域非负实数集
• 定义: 如果存在正数c和n，使得对任意的 $n>=n_0$，都有 $f(n)\le cg(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(max(f_1(n),f_2(n)))$

  • 顺序结构，if 结构，switch 结构

• 乘法规则: $f_1(n)\cdot f_2(n)=O(f_1(n)\cdot f_2(n))$

  • for, while, do-while 结构 (复杂度相乘)
  • 例如：

    for(i=0; i<n; i++)
      for (j=i; j<n; j++)
        k++;
    

    • 上述两个循环的复杂度为 $n^2=n\cdot n$

大Ω表示法

• 定义 :如果存在正数c和 no，使得对所有的 $n\ge n_0$都有 $f(n)\ge cg(n)$, 则称 f(n) 在集合 $\Omega (g(n))$ 中，或简称 $f(n)$ 是 $\Omega (g(n))$ 的，或 $f(n)=\Omega (g(n))$
• 大 O表示法和大 Ω 表示法的唯一区别在于不等式的方向而已
• 采用大 Ω 表示法时，最好找出在函数增值率的所有下限中那个最"紧"(即最大)的下限
  
  
  

$f(n)$值越大, 复杂度增长率越高, 效率越低

时空权衡

• 增大空间开销可能改善算法的时间开销
• 可以节省空间，往往需要增大运算时间