目录
博客:blog.shinelee.me | 博客园 | CSDN
如何评估一个算法的计算时间?
一个算法的实际运行时间很难评估,当时的输入、CPU主频、内存、数据传输速度、是否有其他程序在抢占资源等等,这些因素都会影响算法的实际运行时间。为了公平地对比不同算法的效率,需要脱离开这些物理条件,抽象出一个数学描述。在所有这些因素中,问题的规模往往是决定算法时间的最主要因素。因此,定义算法的时间复杂度(T(n)),用来描述算法的执行时间随着输入规模的增长将如何变化,增长速度是怎样的。
在输入规模较小时,运行时间本来就少,不同算法的差异不大。所以,时间复杂度通常关注的是输入规模(n)较大时运行时间的变化趋势,称之为渐进复杂度,采用大O记号,表示渐进上界,对于任意的(n >> 2),若有常数(c)和函数(f(n))满足T(n)≤c⋅f(n) 则记作 T(n)=O(f(n))
可以简单地认为,O(f(n))表示运行时间与f(n)成正比,比如O(n^2)表示运行时间与输入规模的平方成正比,这样讲虽然并不严谨,但一般情况下无伤大雅。
在n很大时,常数c变得无关紧要,不同算法间的比较主要关注f(n)部分的大小。比如,在(n >> 100)时,(n^2)要比(100n)大得多,因此重点关注(n^2)和(n)增长速度的差异即可。
不同时间复杂度的增长速度对比如下,图片来自Big-O Cheat Sheet Poster,
除了大(O)记号,还有大Ω记号和Θ记号,分别表示下界和确界,
Ω(f(n)):c⋅f(n)≤T(n)Θ(f(n)):c1⋅f(n)≤T(n)≤c2⋅f(n)
他们的关系如下图所示,图片截自邓俊辉-数据结构C++描述第三版
下面汇总摘录了常用数据结构操作和排序算法的复杂度,来源见引用。其中包含最坏时间复杂度、平均时间复杂度以及空间复杂度等,对于排序算法还含有最好时间复杂度。
渐进复杂度分析的是输入规模较大时的情况,输入规模较小时呢?
在输入规模较小时,就不能轻易地忽略掉常数(c)的作用,如下图所示,图片来自Growth Rates Review。复杂度增长快的在输入规模较小时可能会小于复杂度增长慢的。
所以在选择算法时,不能无脑上看起来更快的高级数据结构和算法,还得具体问题具体分析,因为高级数据结构和算法在实现时往往附带额外的计算开销,如果其带来的增益无法抵消掉隐含的代价,可能就会得不偿失。
这同时也给了我们在代码优化方向上的启示,
以上