算法笔记-算法效率分析基础

Posted by MaggicQ on July 1, 2017

算法效率分析

考虑算法运行时间的度量单位,应该找出算法中最重要的操作,即所谓的基本操作(basic operation),

他们对总运行时间的贡献最大,然后计算他们的运行次数。

对算法的效率分析包括三个方面:

  • 最优效率
  • 最差效率
  • 平均效率,必要性:有很多重要的算法的平均效率比他们的最差效率要好很多。

渐进符号

$O(g(n))$ 是增长次数小于等于 $g(n)$ (及其常数倍, $n$ 趋向于无穷大)的函数集合。举几个例子:$ n \in O(n^2) ,100n + 5 \in O(n^2), n^2-2n \in O(n^2)$

$\Omega(g(n))$ 代表增长次数大于等于 $g(n)$ 的函数集合。$\Theta(g(n))$ 是增长次数等于 $g(n)$ 的函数集合。

我们用这些渐进符号来衡量算法的效率。

特性:

2018-12-25 16-42-04屏幕截图

利用极限比较增长次数

2018-12-25 16-44-29屏幕截图

基本的渐进效率类型

2018-12-25 16-59-27屏幕截图

分析非递归算法效率的通用方案

  • 决定用哪个参数表示输入规模
  • 找出算法的基本操作(一般位于算法的最内层循环中)
  • 检查基本操作的执行次数是否只依赖于输入规模,如果它还依赖于一些其他的特性,则最差效率、平均效率以及最优效率需要分别研究
  • 建立一个算法基本操作执行次数的求和表达式
  • 利用求和运算的标准公式和法则来建立一个操作次数的闭合公式,或者至少确定它的增长次数

分析递归算法时间效率的通用方案

  • 决定用哪个参数作为输入规模的度量标准
  • 找出算法的基本操作
  • 检查基本操作的执行次数是否只依赖于输入规模,如果它还依赖于一些其他的特性,则最差效率、平均效率以及最优效率需要分别研究
  • 对于算法基本操作的执行次数,建立一个递推关系以及相应的初始条件
  • 解这个递推式,或者至少确定它的解的增长次数

我们应该谨慎使用递归算法,因为他们的简洁可能会掩盖其低效率的事实。