首页 > Python算法 > 认识算法 阅读数:47

时间复杂度的概念与计算

一个高级语言编写的程序的运行时间主要取决于三个因素:算法的方法、策略(复杂度),问题的输入规模,计算机执行指令的速度。

问题的输入规模是客观的、限定的,要加快算法的效率绝不能影响问题的输入规模;计算机执行指令的速度虽然可以有显著提升,但其发展时间较长,也不是确定的,总不能终日盼着计算机性能的提升。所以提高算法的效率,减少程序运行时间,改进算法的策略是至关重要的。

在讲解时间复杂度之前,需先引入一个概念——时间频度。时间频度代表一个算法中的语句执行次数,其又称为语句频度。显然,时间频度越高的算法运行的时间越长。

时间频度也可被记为 T(n),其中 n 为问题的规模,即输入值的规模。当 n 不断变化时,时间频度 T(n) 也会不断变化。为了探究自变量 n 和因变量 T(n) 变化的关系,我们引入时间复杂度这个概念。不同于时间频度,时间复杂度考察的是当输入规模趋于无穷时,时间频度的渐近情况。

时间复杂度的具体定义为:若有某个辅助函数 f(n),使得 T(n)/f(n) 的极限值(当 n 趋近于无穷大时)为不等于 0 的常数,则称 f(n) 是 T(n) 的同数量级函数。记作

T (n)=O(f(n))

O(f(n)) 称为算法的渐进时间复杂度,简称时间复杂度。在数学上,O 符号(Landau符号)用来描述一个函数数量级的渐近上界。因为 O 符号表示法并不是真实代表算法的执行时间,而是表示代码执行时间的增长变化趋势。

时间复杂度是渐进的

如果我们将算法中的一次计算记为 1,那么如果有 n 个输入值,算法对每一个输入值做一次运算,那么整个算法的运算量即为 n。这个时候,我们就可以说,这是一个时间复杂度为 O(n) 的算法。同理,如果仍有 n 个输入值,但算法对每一个输入值做一次运算,这个操作需要再重复 n 次,那么整个算法的运算量即为 n*n=n2,时间复杂度为 O( n2 )。

这时如果对每一个输入值做一次运算,这个操作需要重复 n+1 次,算法运算量变为:

n i(n+1)=n2+n


这时的时间复杂度是否变为 O( n2 +n)?上文曾提到时间复杂度考察的是当输入量趋于无穷时的情况,所以当 n 趋于无穷的时候,n对算法运行时间占主导地位,而 n 在 n面前就无足轻重,不计入时间复杂度中。换句话说,n2+n 渐近地(在取极限时)与 n相等。

此外,就运行时间来说, n 前面的常数因子远没有输入规模 n 的依赖性重要,所以是可以被忽略的,也就是说 O(n2) 和是时间复杂度相同的,都为 O(n2)。

经过上面的介绍,我们已经对时间复杂度的概念与计算有了简单了解,下面我们就进行实例操作,我们通过《简单Python程序的时间复杂度分析》这一节具体介绍。