复杂度就是用来衡量算法的效率的
一.算法效率
算法效率分析为两种:时间效率和空间效率,对应的就是时间复杂度和空间复杂度。时间复杂度主要衡量的是一个算法的运行速度,而空间复杂度主要衡量一个算法所需要的额外空间。现在计算机的存储以及很大了,所以不再特别关注一个算法的空间复杂度
二.时间复杂度
1.概念
2.大O的渐进表示法
实际我们计算时间复杂度时,并不用计算精确的执行次数,只需要大概执行次数,所以使用大渐进表示法。
3.推到大O阶方法
1.用常数1取代运行时间中的所有加法常数
2.在修改后的运行次数函数中,只保留最高阶项
3.如果最高项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶
使用大O表示法后,func1的时间复杂度为:O(N^2)
4.常见时间复杂度计算举例
1.
2N+10 = O(N)
2.
O(M+N)
3.
100 = O(1)
4.
(n-1)+(n-2)+(n-3)+……+3+2+1
因为(n-1)+1=n,(n-2)+2=n
这里一共有(n-1)/2个n
所以(n-1)+(n-2)+(n-3)+……+3+2+1=(n-1)*n/2 = 1/2*n^2-1/2n = O(n^2)
5.
6.
递归复杂度=递归次数*每次递归执行的次数
这里调用了N次递归方法
所以时间复杂度=O(N)
7.
这里是一个等比数列求和
所以时间复杂度=O(2^n)
5.常见时间复杂度
三.空间复杂度
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。空间复杂度不是程序占用了多少bytes的空间,而是变量的个数。空间复杂度计算规则也使用大O渐进表示法
实例1
使用了一个n+1长的数组--空间复杂度=O(n)
实例2
调用了n次方法
所以空间复杂度=O(n)