算法性能分析

 

1.究竟什么是时间复杂度

时间复杂度是一个函数,它定性描述该算法的运行时间。假设算法的问题规模为n,那么操作单元数量便用函数f(n)来表示,随着数据规模n的增大,算法执行时间的增长率和f(n)的增长率相同,这称作为算法的渐近时间复杂度,简称时间复杂度,记为 O(f(n))

2.什么是大O

算法导论给出的解释:大O用来表示上界的,当用它作为算法的最坏情况运行时间的上界,就是对任意数据输入的运行时间的上界。

 

3.不同数据规模的差异

 

所以我们说的时间复杂度都是省略常数项系数的,是因为一般情况下都是默认数据规模足够的大,基于这样的事实,给出的算法时间复杂的的一个排行如下所示:

O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(nlogn)线性对数阶 < O(n^2)平方阶 < O(n^3)立方阶 < O(2^n)指数阶

但是也要注意大常数,如果这个常数非常大,例如10^7 ,10^9 ,那么常数就是不得不考虑的因素了。

4.复杂表达式的化简

有时候我们去计算时间复杂度的时候发现不是一个简单的O(n) 或者O(n^2), 而是一个复杂的表达式,例如:

O(2*n^2 + 10*n + 1000)

 

那这里如何描述这个算法的时间复杂度呢,一种方法就是简化法。

去掉运行时间中的加法常数项 (因为常数项并不会因为n的增大而增加计算机的操作次数)。

O(2*n^2 + 10*n)

去掉常数系数(上文中已经详细讲过为什么可以去掉常数项的原因)。

O(n^2 + n)

只保留保留最高项,去掉数量级小一级的n (因为n^2 的数据规模远大于n),最终简化为:

O(n^2)

如果这一步理解有困难,那也可以做提取n的操作,变成O(n(n+1)) ,省略加法常数项后也就别变成了:

O(n^2)

所以最后我们说:这个算法的算法时间复杂度是O(n^2) 。

也可以用另一种简化的思路,其实当n大于40的时候, 这个复杂度会恒小于O(3 × n^2), O(2 × n^2 + 10 × n + 1000) < O(3 × n^2),所以说最后省略掉常数项系数最终时间复杂度也是O(n^2)

通俗的讲就是忽略量级低的,因为数据量足够大的时候量级底的相当于没有---高数里是这样。

5.O(logn)中的log是以什么为底?

 

热门相关:补天记   一等狂妃:邪王,请接招!   我是仙凡   重生之嫡女祸妃   紫府仙缘