算法的时间复杂度和空间复杂度

2021-03-26 本文已影响0人庄周幻梦

算法

算法 (Algorithm)是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的额方法描述解决问题的策略机制。不同的算法可能用不同的时间，空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度和时间复杂度来衡量。

时间复杂度和空间复杂度

时间复杂度和空间复杂度:
- 时间复杂度：是指执行当前算法所消耗的时间。
- 空间复杂度：是指执行当前算法需要占用多少内存空间。

因此，评价一个算法的效率主要是看它的时间复杂度和空间复杂度情况。然而，有的时候时间和空间却又是鱼和熊掌，不可兼得的，那么我们就需要从中去取一个平衡点。

时间复杂度

我们想要知道一个算法的「时间复杂度」，很多人首先想到的的方法就是把这个算法程序运行一遍，那么它所消耗的时间就自然而然知道了。

这种方式可以吗？当然可以，不过它也有很多弊端。
这种方式非常容易受运行环境的影响，在性能高的机器上跑出来的结果与在性能低的机器上跑的结果相差会很大。而且对测试时使用的数据规模也有很大关系。再者，并我们在写算法的时候，还没有办法完整的去运行呢。

因此，另一种更为通用的方法就出来了：[ 大O符号表示法 ]，即 T(n) = O(f(n))

我们先来看个例子：

m = 0
for i in range(n + 1):
    m += i

通过 [大O符号表示法]，这端代码的时间复杂度为：O(n) , 为什么呢？
在大O表示法中，时间复杂度的公式是：T(n) = O(f(n))，其中f(n)表示每行代码执行次数之和，而O表示正比例关系，这个公式的全称是：算法的渐进时间复杂度。

假设每行代码的执行时间都是一样的，我们用1颗粒时间来表示，那个这个例子第一行耗时是1个颗粒时间，第二/三行的执行时间是n个颗粒时间，那么总时间就是1颗粒时间+ 2 * n颗粒时间。

即T(n) = (1+2n)*颗粒时间，从这个结果可以看出这个算法的耗时是随着n的变化而变化，因此，我们可以简化的将这个算法的时间复杂度表示为: T(n)=O(n)

为什么可以这么去简化呢，因为大O符号表示法并不是用于来真是代表算法的执行时间的，它是用来执行代码执行时间段额增长变化趋势的。

所以当n无限大的时候， T(n) 中常量1 和倍数2意义已经不大了，因此可以简化为T(n) = O(n)。

常见时间复杂度量级：

常数阶 O(1)
对数阶 O(logN)
线性阶 O(n)
线性对数阶 O(nlogN)
平方阶 O(n²)
立方阶 O(n³)
K次方阶 O(n^K)
指数阶 O(2^n)

从上往下依次的时间复杂度越来越大，执行的效率越来越低。

常用的时间复杂度例子：

常数阶 O(1)
```
a = 1
b = 2
a += 1
b += 1
m = a+b
```
上述代码在执行的时候，它消耗的时间并不随着某个变量的增长而增长，那么无论这类代码有多长，即时有几万几十万行，都可以用O(1)来表示它的时间复杂度。
对数阶 O(logN)
```
i = 1
while(i<n):
    i*=2
```
上述代码在执行的时候，while循环里面，每次都将i乘以2，乘完之后，i距离n 就越来越近了。假设循环x次之后，i就大于n了，此时这循环就退出了，也就是说2的x次方等于n。

那么 x = log2^n, 也就是说当循环log2^n次以后，这段代码就结束了。因此这段代码的时间复杂度为：O(logn)

线性阶 O(n)

m = 0
for i in range(n + 1):
    m += i

线性对数阶 O(nlogN)
```
for m in range(N)：
        i = 1
        while(i<n):
            i*=2
```
上述代码在执行的时候，for循环里面的代码是对数阶的时间复杂度，因此线性对数阶其实就是将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是n*O(logn)=>O(nlogN)
平方阶 O(n²), 立方阶O(n³)，K次方阶O(n^K)
```
a = 0
while a < n:
    a += 1
    b = 0
    while b < n:
        b += 1
```
上述代码是个平方阶的例子，可以看出，实际上就是嵌套了两层n循环，它的时间复杂度就是O(n*n)=O(n²)。立方阶和K次方阶同理即K层n循环。

空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度，同样反映的是一个趋势，我们用S(n)来定义。

空间复杂度比较常用的有：O(1), O(n), O(n2)

# 空间复杂度为 O(1)
a = 'python'
# 空间复杂度为 O(5) => O(n)
num1 = [1, 2, 3, 4, 5]
# 空间复杂度为 O(3*5) => 如果每个列表的元素数量一样的话 O(n²)
num2 = [[1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5]]
# 空间复杂度为 O(3*3*3) => 如果每个列表的元素数量一样的话 O(n³)
num3 = [[[1, 2, 3], [1, 2, 3], [1, 2, 3]], [[1, 2, 3], [1, 2, 3], [1, 2, 3]], [[1, 2, 3], [1, 2, 3], [1, 2, 3]]]

原文链接：https://zhuanlan.zhihu.com/p/50479555
＞如有侵权，请联系删除