时
间频
度
：一
个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。
一个算法中的语句执行次数称为语句频度或时间频度
。记为
T(n)
时间复杂度
一
般情况下，算法中的基本操作语句的重复执行次数是问题规模
n
的某个函数，用
T(n)
表示，若有某个辅助函数
f(n)
，使得当
n
趋近于无穷大时，
T(n) / f(n)
的极限值为不等于零的常数，则称
f(n)
是
T(n)
的同数量级函数。记作
T(n)=
Ｏ
( f(n) )
，称Ｏ
( f(n) )
为算法的渐进时间复杂度，简称时间复杂度
。
T(n
)
不同，但时间复杂度可能相同。 如：
T(n)=
n²+7n+6
与
T(n)=
3n²+2n+2
它们的
T(n)
不同，但时间复杂度相同，都为
O(n²)
。
计
算时间复杂度的方
法：
用常数
1
代替运行时间中的所有加法常数
T(n)=n²+7n+6
=>
T(n)=
n²+7n+1
修改后的运行次数函数中，只保留最高阶项
T(n)=
n²+7n+1 => T(n) = n²
去除最高阶项的系
数
T(n) =
n²
=> T(n) = n² => O(
n²
)
常见的时间复杂度
1)
常
数阶
O(1
)
无
论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是
O(1
)
上述代码在执行的时候，它消耗的时候并不随着某个变量的增长而增长，那么无论这类代码有多长，即使有几万几十万行，都可以用
O(1)
来表示它的时间复杂度。
2)
对数阶
O(
log
2
n
)
说明
：在
while
循环里面，每次都将
i
乘以
2
，乘完之后，
i
距离
n
就越来越近了
。假
设循环
x
次之后，
i
就大于
2
了，此时这个循环就退出了，也就是说
2
的
x
次方等于
n
，那么
x =
log
2
n
也
就是说当循环
log
2
n
次以后，这个代码就结束了。因此这个代码的时间复杂度为：
O(
log
2
n
)
。
O(
log
2
n
)
的这个
2
时间上是根据代码变化的，
i
=
i
* 3
，则是
O(
log
3
n
) .
3)
线
性阶
O(n)
说明
：这
段代码，
for
循环里面的代码会执行
n
遍，因此它消耗的时间是随着
n
的变化而变化的，因此这类代码都可以用
O(n)
来表示它的时间复杂度
4)
线
性对数阶
O(
nlogN
)
说明
：线
性对数阶
O(
nlogN
)
其实非常容易理解，将时间复杂度为
O(
logn
)
的代码循环
N
遍的话，那么它的时间复杂度就是
n * O(
logN
)
，也就是了
O(
nlogN
)
5)
平
方阶O(n²)
说明
：平
方阶
O(n²)
就更容易理解了，如果把
O(n)
的代码再嵌套循环一遍，它的时间复杂度就是
O(n²
)
，
这段代码其实就是嵌套了
2
层
n
循环，它的时间复杂度就是
O(n*n)
，即
O(n²)
如
果将其中一层循环的
n
改成
m
，
那它的时间复杂度就变成了
O(m*n)
6)
立
方阶
O(n³)
、
K
次方阶
O(
n^k
)
说明
：参
考上面的
O(n²)
去理解就好了，
O(n³)
相当于三层
n
循环，其它的类似
平
均时间复杂度和最坏时间复杂度
平
均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，该算法的运行时间
。
最
坏情况下的时间复杂度称最坏时间复杂度。一般讨论的时间复杂度均是最坏情况下的时间复杂度。 这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限，这就保证了算法的运行时间不会比最坏情况更长
。
平均
时间
复杂度和
最
坏时间复杂度
是
否一致，和算法有关
(
如图
🙂
。
空间复杂度简介
类
似于时间复杂度的讨论，一个算法的空间复杂度
(Space
Complexity)
定
义为该算法所耗费的存储空间，它也是问题规模
n
的函数
。
空间复杂度
(Space Complexity)
是对一个算法在运行过程中临时占用存储空间大小的量度
。有
的算法需要占用的临时工作单元数与解决问题的规模
n
有关，它随着
n
的增大而增大，当
n
较大时，将占用较多的存储单元，例
如快
速排序和归并排序算法就属于这种情
况
在做算法分析时，
主要讨论的是时间复杂度
。从用户使用体验上看，更看重的程序执行的速度。一些缓存产品
(
redis
,
memcache
)
和算法
(
基数排序
)
本质就是用空间换时间
.