一文吃透时间复杂度和空间复杂度

关注
发布于: 2020 年 07 月 23 日
学习数据结构和算法的第一步
﻿
时间复杂度最常见的时间复杂度有哪几种O(1)：Constant Complexity 常数复杂度
O(log n)：Logarithmic ComPlexity 对数复杂度
O(n)：Linear ComPlexity 线性时间复杂度
O(n^2)：N square ComPlexity 平方
O(n^3)：N cubic ComPlexity 立方
O(2^n)：Exponential Growth 指数
O(n!)：Factorial 阶乘
﻿
分析时间复杂度的时候是不考虑前边的系数的，比如说O(1)的话，并不代表它的复杂度是1，也可以是2、3、4...,只要是常数次的，都用O(1)表示
﻿
如何来看一段代码的时间复杂度？最常用的方式就是直接看这段代码，它根据n的不同情况会运行多少次
O(1)
$n=100000;
echo 'hello';
﻿
O(?)
$n=100000;
echo 'hello1';
echo 'hello2';
echo 'hello3';
第一段代码，不管n是多少，都只执行一次，所以它的时间复杂度就是O(1)。第二个其实也同理，我们不关心系数是多少。虽然第二段代码会执行3次echo输出，但是不管n是多少，它都只执行3次，因此它的时间复杂度也是常数复杂度，也就是O(1)
﻿
在看下边两段代码：
O(n)
for($i = 1; $i <= $n; $i++) {
    echo 'hello';
}
﻿
O(n^2)
for($i = 1; $i <= $n; $i++) {
    for($j = 1; $j <= $n; $j++) {
        echo 'hello';
    }
}
这两段代码都是随着n的不同，它执行的次数也在发生变化，第一段代码执行的次数和n是线性关系的，所以它的时间复杂度是O(n)。
﻿
第二段代码是一个嵌套循环，当n为100的情况下，里边的输出语句就会执行10000次，因此它的时间复杂度就是O(n^2)。如果第二段代码中的循环不是嵌套的，而是并列的，那么它的时间复杂度应该是O(2n)，因为前边的常数系数我们不关注，因此它的时间复杂度就是O(n)
﻿
O(log n)
for($i = 1; $i <= $n; $i = $i*2) {
    echo 'hello';
}
﻿
O(k^2)
﻿
fib($n) {
    if ($n < 2) {
        return $n;
    }
    
    return fib($n-1) + fib($n-2);
}
 第一段代码，当n=4时，循环执行2次，所以循环内部执行的次数和n的关系为log2(n)，因此时间复杂度为对数复杂度O(logn)。第二段是一个Fibonacci(斐波拉契)数列，这里是用了递归的这种形式，这就牵扯到了递归程序在执行的时候，如何计算它的时间复杂度，它的答案是k^n，k是一个常数，是一个指数级的，所以简单的通过递归的方式求Fibonacci数列是非常慢的，它是指数级的时间复杂度。具体指数级的时间复杂度是怎么得到的，后边会详细说明。下边看一下各种时间复杂度的曲线
﻿
﻿
从这张图中可以看到，当n比较小的时候，在10以内的话，不同的时间复杂度其实都差不多。但是如果当n继续扩大，指数级的增长是非常快的。因此，当我们在写程序的时候，如果能优化时间复杂度，比如说从2^n降到n^2的话，从这个曲线来看，当n较大的时候，得到的收益是非常高的。因此这也告诉我们，在平时开发业务代码的时候，一定要对自己的时间和空间复杂度有所了解，而且是养成习惯，写完代码之后，下意识的分析出这段程序的时间和空间复杂度。
﻿
从图中可以看到，如果你的时间复杂度写砸了的话，其实带给公司的机器或者说资源的损耗，随着n的增大的话，是成百上千的增加，而如果你能简化的话，对公司来说是节约很多成本的
﻿
对于不同的程序，在写法当中完成同样的目标，它可能会导致时间复杂度的不一样。下边看一个简单的例题
从1加到2一直加到n，求它的和
小学学数学的时候，大家都知道了有两种方法，方法一的话用程序暴力求解的话，就是从1循环到n累加。这个是一层循环，n为多少，就执行多少次累加，所以它的时间复杂度就是O(n)
$sum = 0;
for ($i=1; $i <=$n; $i++) {
    $sum += $i;
}
﻿
方法二就是使用一个数学的求和公式：
y = n*(n+1)/2
用这个公式，发现程序就只有一行了，所以它的时间复杂度就是O(1)了。所以可以看到，程序的不同方法，最后得到的结果虽然是一样的，但是它的时间复杂度很不一样
﻿
对于递归这种，如何分析时间复杂度？递归的话，关键就是要了解它的递归过程，总共执行了递归语句多少次。如果是循环的话，很好理解，n次的循环就执行了n次。那么递归的话，其实它是层层嵌套，其实很多时候，我们就是把递归它的执行顺序，画出一个树形结构，称之为它的递归状态的递归树。以前边的求Fibonacci(斐波拉契)数列的第n项为例
Fib：0,1,1,2,3,5,8,13,21...
﻿
F(n) = F(n-1)+F(n-2)
我之前面试的时候遇到过这么一道题，写的是最最简单的用递归的方式实现
fib($n) {
    if($n < 2) {
        retuen $n;
    }
    
    return fib($n-1)+fib($n-2);
} 
前边有说到它的时间复杂度是O(k^n)，那么怎么得到的，可以分析一下，假设此时n取6，要计算Fib(6)，就看这段代码如何执行
﻿
﻿
所以，如果想计算F(6)就引出两个分支，F(5)和F(4)，至少多出了两次运算
﻿
如果要计算F(5)可同理得到，需要结算F(4)和F(3)。如果要计算F(4)可同理得到，需要结算F(3)和F(2)。这里就可以看到两个现象：
每多展开一层的话，运行的节点数就是上边一层的两倍，第一层只有1个节点，第二层有2个节点，第三层就有4个节点，再下一层就是8个节点。所以它每一层的话，它的节点数，也就是执行次数，是成指数增长的。由此可见，到n的时候，它就执行了2^n次
第二个可以观察到，有重复的节点出现在了执行的树里边，比如图中的F(4)和F(3)。如果将这个树继续展开，会发现F(4)、F(3)、F(2)都会被计算了很多次
﻿
正是因为有这么多大量冗余的计算，导致求6个数的Fibonacci数的话，就变成了2^6次方这么一个时间复杂度。因此在面试中遇到这类题，尽量别用这种方式写，否则怕是直接凉凉了。可以加一个缓存，把这些中间结果能够缓存下来（用数组或哈希存起来，有重复计算的数值，再从里边找），或者直接用一个循环来写
﻿
主定理介绍一个叫主定理的东西，这个定理为什么重要，就是因为这个主定理的话，其实它是用来解决所有递归的函数，怎么来计算它的时间复杂度。主定理本身的话，数学上来证明相对比较复杂（关于主定理可以参考维基百科：https://zh.wikipedia.org/wiki/%E4%B8%BB%E5%AE%9A%E7%90%86）
﻿
也就是说，任何一个分治或者递归的函数，都可以算出它的时间复杂度，怎么算就是通过这个主定理。本身比较复杂的话，那怎样化简为实际可用的办法，其实关键就是这四种，一般记住就可以了
﻿
﻿
一般在各种递归的情形的话，有上边这四种情形，是在面试和平时工作中会用上
﻿
二分查找(Binary search)：一般发生在一个数列本身有序的时候，要在有序的数列中找到目标数，所以它每次都一分为二，只查一边，这样的话，最后它的时间复杂度是O(logn)
﻿
二叉树遍历(Binary tree traversal)：如果是二叉树遍历的话，它的时间复杂度为O(n)。因为通过主定理可以知道，它每次要一分为二，但是每次一分为二之后，每一边它是相同的时间复杂度。最后它的递推公式就变成了图中T(n)=2T(n/2)+O(1)这样。最后根据这个主定理就可以推出它的运行时间为O(n)。当然这里也有一个简化的思考方式，就是二叉树的遍历的话，会每一个节点都访问一次，且仅访问一次，所以它的时间复杂度就是O(n)
﻿
二维矩阵(Optimal sorted matrix search)：在一个排好序的二维矩阵中进行二分查找，这个时候也是通过主定理可以得出时间复杂度是O(n)，记住就可以了
﻿
归并排序(merge sort)：所有排序最优的办法就是nlogn，归并排序的时间复杂度就是O(nlogn)
﻿
常见的关于时间复杂度的面试题二叉树的遍历-前序、中序、后序：时间复杂度是多少？
﻿
答案是：O(n)，这里的n代表二叉树里边树的节点的总数，不管是哪种方式遍历，每个节点都有且仅访问一次，所以它的复杂度是线性于二叉树的节点总数，也就是O(n)
﻿
图的遍历：时间复杂度是多少？
﻿
答案：O(n)，图中的每一个节点也是有且仅访问一次，因此时间复杂度也是O(n)，n为图中的节点总数
﻿
搜索算法：DFS(深度优先)、BFS(广度优先)时间复杂度是多少？
﻿
答案：O(n)，后边的文章会详细介绍这两种算法(n为搜索空间中的节点总数)
﻿
二分查找：时间复杂度是多少？
﻿
答案：O(logn)
﻿
空间复杂度空间复杂度和时间复杂度的情况其实类似，但是它更加的简单。用最简单的方式来分析即可。主要有两个原则：
﻿
如果你的代码中开了数组，那么数组的长度基本上就是你的空间复杂度。比如你开了一个一维的数组，那么你的空间复杂度就是O(n)，如果开了一个二维的数组，数组长度是n^2，那么空间复杂度基本上就是n^2
﻿
如果是有递归的话，那么它递归最深的深度，就是你空间复杂度的最大值。如果你的程序里边递归中又开了数组，那么空间复杂度就是两者的最大值
﻿
在快速变化的技术中寻找不变，才是一个技术人的核心竞争力。知行合一，理论结合实践
﻿