算法的时间、空间复杂度如何比较？
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
-
50
点击蓝色“ 乔志勇笔记 ”关注我哟 加个“ 星标 ”，第一时间获取推送...
-
42
1. 博客背景 今天有同事在检查代码的时候，由于函数写的性能不是很好，被打回去重构了，细思极恐，今天和大家分享一篇用js讲解的时间复杂度和空间复杂度的博客 2. 复杂度的表示方式 之前有看过的，你可能...
-
20
目录 一、时间复杂度：执行算法所需要的计算工作量 （一）时间复杂度的理解 2.（渐进）时间复杂度定义 （二）时间复杂度的计算
-
17
本文是覃超老师的《算法训练营》的学习笔记，此笔记的内容包含了学习后的个人记录、个人总结、理解和思想。从而更好的学习算法。 前言 学习任何一门知识的时...
-
9
各种排序算法时间复杂度和空间复杂度表 各种排序算法时间复杂度和空间复杂度表: 各种排序算法时间复杂度和空间复杂度表 比较时间复杂度函数的情况如下图： 比较时间复杂度函数的情况...
-
13
关注公众号「五分钟学算法」，回复关键字 算法，获取谷歌工程师的 LeetCode 算法笔记。...
-
5
针对某一类问题的解决，我们可能需要借助算法来实现，实现的手段也可能是各式各样的。虽然最终都解决了问...
-
14
在使用当中，算法效率分为两种，一是时间效率(时间复杂度)，二是空间效率(空间复杂度)。时间复杂度是指程序运行的速度。空间复杂度是指一个算法所需要的额外的空间。 时间复杂度 什么是时间复杂度 计算程序运行的时间不能拿简单的...
-
5
作为一名“程序猿”，大家应该都听过这么一句话：程序=数据结构+算法。 这句话是由瑞士计算机科学家尼古拉斯·沃斯（Niklaus Wirth）在 1984 年获得图灵奖时说的一句话，这位大佬还以这句话为名出了一本书《Algorithms + Data Structures=Programs》，从此...
-
4
那些年忽略的知识：时间复杂度和空间复杂度详解 尴尬，学妹问我...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK