写点什么

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

用户头像
书旅
关注
发布于: 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



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



在快速变化的技术中寻找不变,才是一个技术人的核心竞争力。知行合一,理论结合实践



发布于: 2020 年 07 月 23 日阅读数: 84
用户头像

书旅

关注

公众号:IT猿圈 2019.04.11 加入

还未添加个人简介

评论

发布
暂无评论
一文吃透时间复杂度和空间复杂度