乐趣区

关于算法-数据结构:一文吃透时间复杂度和空间复杂度

jiezi

学习数据结构和算法的第一步

工夫复杂度

最常见的工夫复杂度有哪几种

  • 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…）

也就是说，任何一个分治或者递归的函数，都能够算出它的工夫复杂度，怎么算就是通过这个主定理。自身比较复杂的话，那怎么化简为理论可用的方法，其实要害就是这四种，个别记住就能够了

个别在各种递归的情景的话，有上边这四种情景，是在面试和平时工作中会用上

二分查找(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

如果是有递归的话，那么它递归最深的深度，就是你空间复杂度的最大值。如果你的程序里边递归中又开了数组，那么空间复杂度就是两者的最大值

在疾速变动的技术中寻找不变，才是一个技术人的外围竞争力。知行合一，实践联合实际

退出移动版