概念
我们只需要考虑当问题规模无穷大的时候的程序复杂度就行了，那么什么是渐进复杂度呢？
本章将会看到各种复杂度的定义，如图所示
各种复杂度
包括
常数复杂度、对数复杂度、线性复杂度、对数线性复杂度、多项式复杂度、指数复杂度，这几种
特别注意
人们有时候特别容易搞混多项式复杂度和指数复杂度
最后这两者的复杂度，区别在于，多项式复杂度当中，指数是常数，所以不同的多项式算法像
2c 和3c 都是底数在变，所以是渐进于某个
而指数复杂度，如 c2 和c3 都是指数在变，所以是渐进于某个常数的n次幂
n代表问题规模的大小
请注意，该列表从上到下基本上是从算法复杂度递增的方向来描述的
如此，我们应该尽可能使用列表当中考前的简单算法
对数算法
每次将问题一分为二，实际上是一个特别好的对数算法，我们前面在用二分法查找平方根的时候用到的就是这样的对数复杂度的方法。实际上，我们在二分查找列表当中的元素时也是用的这个方法
对数复杂度
在这个题里面，因为只有i的位数影响算法复杂度，而不是i的实际大小，所以取对数就可以的到i的位数大小，故这是一个对数复杂度的问题
线性算法
由于我们只关心最大的复杂度
由于我们只关心最大的复杂度，在这个题当中，于循环中查找也就变成了线性的复杂度
网友评论