算法的时间、空间复杂度如何比较？
source link: https://blog.51cto.com/u_15740457/5979035
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
算法的时间、空间复杂度如何比较？
精选 原创一、时间复杂度BigO
首先我们不能以机器运行算法的时间来评判一个算法的时间复杂度，因为即使是相同的算法在不同机器上（机器的个体差异性）运行时间都可能不尽相同，因此我们采用
【大O表示法】——算法的渐进复杂度T（n）=O（f（n））。
首先解读这个公式，f（n）表示代码执行的次数，O表示正比例关系，而T（n）就表示算法的渐进复杂度（就是当一个问题量级增加的时候，算法运行时间增长的一个趋势）。
{
x++;
}
请问这个代码块执行几次？
答：3N+1次
首先开头定义i=1，执行一次，后面在循环中就不参与，而i<=n,x++,i++各执行N次，所以相加就是3N+1次。
O（3N+1）=O（N），因为这个公式计算的是当n无限接近于正无穷时，可以省略1和3.
上面的代码执行N^2次
上面的代码原则上是执行N+N^2次，而又因为N是趋近于无穷的，所以最终结果就是N^2次，即O（N+N^2）=O(N^2)！
常用的时间复杂度量级
横坐标表示代码执行的次数，纵坐标表示时间复杂度量级。
从图中不难看出，n!、2n\、n2时间复杂度都是指数级的，因此代码运行的非常慢。
1、O(1)
上面代码时间复杂度是O（1），因为当其中变量的值增加到任何值，本质交换两个数的值，时间复杂度就是O（1）
2、O（n）
这时复杂度就取决于n的大小
3、O（log n）
这其实是一道数学题，就是2^k=n,求k
两边同取对数，答案即为log n（注意此时的底数都可以忽略不计）
4、O（nlog n）
比较容易理解，外面套了一层循环，就是在原来的基础上*n。
5、o（m*n）
就是for循环嵌套，俗称套娃。
二、空间复杂度
空间复杂度自然也不是计算空间的大小，而是内存空间增长的趋势。
常用的空间复杂度
O（1）、O（n）、O（n^2）
1、O（1）
无论xy增加到多少，内存分配还是不变，因此还是O（1）
2、O（n）
随着n的增加，对数组分配的空间也增多
时间空间复杂度=时间和空间增长的复杂度
- 赞
- 收藏
- 评论
- 分享
- 举报
上一篇：一道map例题
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK