不知‘时间复杂度’所云的看过来

教科书对算法时间复杂度的描述用了很多伟光正的数学语言,说的糊里糊涂,看得让人头晕晕。这样解释看看能否清晰些:

时间复杂度的感性认识:一句话,基本操作执行的次数。一个算法基本操作执行次数越多,时间复杂度越大,反之越小。
但在实际操作中,不会真的就去计算具体执行了多少次,而是先分拣出2方面内容,1是算法的基本操作,如比较,赋值,一次数学运算等。2是影响执行基本操作次数的因素,典型的如循环操作的次数、数组元素个数、被操作元素的数量等。然后,把这些因素定义为n,即推广至一般形式,如数组元素个数为n个,循环执行n次等。再然后就可以写出时间复杂度函数了。步骤如下:

1、确定神马是基本操作。
2、确定神马是影响执行基本操作执行次数的因素,将其定义为n。
3、根据算法可以得出基本操作执行次数的方程式f(n)。
4、取f(n)的最大幂次项,并去常量系数。即取f(n)的数量级。
5、然后用O()包装一下,没别的意思,就是让别人知道这是时间复杂度。

为什么要取数量级而不是直接用执行次数方程式f(n)呢?如果你为了应付考试,死记硬背下来就行了,刨根问底会分散注意力且学习效率不高!如果真的有兴趣就往下看。

其实为表示一般性和通用性,时间复杂度是考察n可以为任意值直至趋向无穷大时基本操作执行的次数,既然去到无穷大这么大了,除了最高幂次项外,其它都是浮云了,常系数也就更不需要了。也就是说,无穷大之间高手过招比较的是数量级,细枝末节统统滚开。用数学八股文描述就是如果g(n)为f(n)的数量级,则f(n)/g(n)当n->无穷大时为一常数,那么g(n)可表示该算法的时间复杂度。

特别地,如果n为确定的常数,则f(n)也为一个确定值,这时定义它的时间复杂度为O(1)。无论n和f(n)的值多么巨大都为O(1)。如:
for i:=1 to 1000000000000 do a:=i;  时间复杂度为O(1)
n:=1; for i:=1 to n do a:=i;  时间复杂度为O(n)

显然前例执行时间更长,但时间复杂度前例比后例小。这就是数学文绉绉玩概念把我们搞S的结果。前例是某一个具体确定的执行过程,时间复杂度总为O(1),它不具有一般性和通用性,时间复杂度对它而言是无意义的。对此类具体的执行过程,精确的执行次数或执行时间才有意义。前例时间复杂度的通用模式就是后例。点到即止,不再深入了。

原文地址:https://www.cnblogs.com/happyfree/p/3668972.html