算法之时间复杂度及空间复杂度
一、介绍
时间复杂度,引入百度的解释
时间频度一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
在刚才提到的时间频度中,n称为问题的规模,当n不断变化时,时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此,我们引入时间复杂度概念。 一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。
空间复杂度
类似于时间复杂度的讨论,一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间,它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。
二、首先了解一下
计算时间复杂度记住这个规律:
- 用常数1取代运行时间中的所有加法常数(3+5+5,都是常数,最后O(1))
- 在修改后的运行次数函数中,只保留最高阶项(2n^3+2n^2+2n,最后O(n^3))
- 如果最高阶存在且不是1,则去除与这个项相乘的常数(1/3n^2 、3n^2,最后都是O(n^2))
下面也是这个说法
对于大数据的比较的话,常常由图曲线等,判断时间复杂度
1、3、99、2000......................等,在算法来说,时间复杂度就是O(1)
2n、3n、9n、2n+1、4n+3......等,在算法来说,时间复杂度就是O(n)
更多的如下图
三、举例子说明怎么计算时间复杂度
根据上述知识点二的了解,下面我简单举三个例子说明计算时间复杂度
1、冒泡排序
次数取决于内层,内层for执行次数:n-1、n-2、n-3......1 一共执行(n-1 + 1)*(n-1)/ 2 即 (n^2-n) / 2
根据二所提的知识,可知,冒泡算法的时间复杂度为O(n^2)
2、如下普通代码
要执行多少次?设要执行x次,则会有2^x = n 所以就有x = log2n
所以该算法时间复杂度为O(logn)
3、复合程序计算时间复杂度
如上图,第一个for语句计算的是方法里面的时间复杂度为:O(n^2)
第二个for直接时间复杂度为O(n)
所以n^2 + n,程序时间复杂度为O(n^2)
四、空间复杂度
有时候可以用空间复杂度来换时间复杂度,比如要计算闰年时,假设只有一个范围,那我可以提前设定一个数组,存放这个范围,设1为标志为闰年,其它就不是。这样子就实现了用空间复杂度来换算法计算闰年,换时间复杂度了。