算法效率衡量

2019-12-02 本文已影响0人晨光523152

执行时间反应算法效率

实现算法程序的执行时间可以反应出算法的效率，即算法的优劣。

但是同一个程序放在不同的机器里执行，会得到不同的时间，所以不能单靠运行的时间来比较算法的优劣并不一定是客观准确的！

虽然每台机器执行的总时间不同，但是执行基本运算数量大体相同。

所以用执行基本运算数量来判断算法效率

时间复杂度与“大0记法”

时间复杂度：假设存在函数g，使得算法A处理规模为n的问题示例所用时间为T(n)=O(g(n))，则称O(g(n))为算法A的渐进时间复杂度，简称时间复杂度，记为T(n)。

对于算法进行特别具体的细致分析虽然很好，但在实践中的实际价值有限。对于算法的时间性质和空间性质，最重要的是其数量级和趋势，这些是分析算法效率的主要部分。（而计量算法基本操作数量的规模函数中那些常量因子可以忽略不记。）

最坏复杂时间度

分析算法时，存在几种可能的考虑:

算法完成工作最少需要多少基本操作，即最优时间复杂度（没有参考价值）
算法完成工作最多需要多少基本操作，即最坏时间复杂度（提供了一种保证，表明算法在此中程度的基本操作中一定能完成工作）
算法完成工作平均需要多少基本操作，即平均时间复杂度（对算法的一个全面评价，完整全面的反映了这个算法的本质。但是这种衡量没有保证，不是每个计算都能在这个基本操作内完成。而且，对于平均情况的计算，也会因为应用算法的实例分布可能不均匀而难以计算）

时间复杂度的几条基本运算规则

基本操作，即只有常数项，认为其时间复杂度为 $\mathcal{O}(1)$
顺序结构，时间复杂度按加法进行
循环结构，时间复杂度按乘法进行
分支结构，时间复杂度取最大值
判断一个算法的效率时，往往只需要关注数量的最高次项，其它次要项和常数项可以忽略
在没有特殊说明时，我们分析的算法时间复杂度都是指最坏时间复杂度

常见时间复杂度

执行次数函数举例	阶	非正式术语
12	$\mathcal{O}(1)$	常数阶
$2n + 3$	$\mathcal{O}(n)$	线性阶
$3n^{2} + 2n + 1$	$\mathcal{O}(n^{2})$	平方阶
$5log_{2}n + 20$	$\mathcal{O}(logn)$	对数阶
$2n + 3nlog_{2}n + 19$	$\mathcal{O}(nlogn)$	$nlogn$ 阶
$6n^{3} + 2n^{2} + 3n + 4$	$\mathcal{O}(n^{3})$	立方阶
$2^{n}$	$\mathcal{O}(2^{n})$	指数阶

note: 经常将 $log_{2}n$ 简写成 $logn$

所消耗的时间从小到大：
$\mathcal{O}(1) < \mathcal{O}(logn) < \mathcal{O}(n) < \mathcal{O}(nlogn) < \mathcal{O}(n^{2}) < \mathcal{O}(n^{3}) < \mathcal{O}(2^{n}) < \mathcal{O}(n!) < \mathcal{O}(n^{n})$

参考资料：https://www.bilibili.com/video/av53583801?p=5