【数据结构与算法】分析时间复杂度与空间复杂度



本文是覃超老师的《算法训练营》的学习笔记,此笔记的内容包含了学习后的个人记录、个人总结、理解和思想。从而更好的学习算法。



前言



学习任何一门知识的时候,我们需要分析清楚这门知识的核心是什么,从而在这个核心中我们可以得到什么。如果我们是盲目的吸收知识,其实很多知识我们都是在目前场景、工作、生活中无法使用的。也是因为学习之后无法运用,所以我们很快就会遗忘,或者是在学习的过程中很容易就会放弃。



在一生的学习的过程中,发现学习我们急需使用或者能给我们及时带来价值的知识,我们会学的更加牢固,更加能坚持学习。



学习《数据结构与算法》这门知识的核心是什么?又能得到什么呢?



  1. 弄懂编程的底层逻辑;

  2. 在编程的过程中,拥有一个哆啦A梦一样百宝工具袋;

  3. 在遇到性能问题的时候,有算法的思维逻辑和规则来解决问题;

  4. 提高编程思维;



这篇笔记记录了算法的核心 时间和空间复杂度 ,《数据结构与算法》都是围绕着这个核心开展的。它的存在也是为了解决我们在编程的过程中性能问题,同时也让我们有更高级的思维和思路,写出更优质的程序。





复杂度指标 Big O Notation



  • O (1): 常数复杂度 – Constant Complexity

  • O (log n): 对数复杂度 – Logarithmic Complexity

  • O (n): 线性复杂度 – Linear Complexity

  • O (n^2): 平方复杂度 – N square Complexity

  • O (2^n): 指数 – Exponential Growth

  • O (n!): 阶乘 – Factorial



如何看时间复杂度



  • 分析函数;

  • 根据n的不同情况会运行多少次;

  • 最后得出一个平均的运行次数的量级;



Complexity 例子



O (1) – 常数复杂度



letn =1000;
console.log("Hello - your input is: "+ n)



O (N) – 线性复杂度



for(leti =1; i <= n; i++) {
console.log("Hello world - your input is: "+ i)
}



O (N^2)



for(leti =1; i <= n; i++) {
for(letj =1; j <= n; j++) {
console.log("Hello world - your input is: "+ i +" and "+ j)
}
}



那如果我们不是嵌套两层 for 循环,是把两个循环分开来存放呢?这种方式时间复杂度是?



for(leti =1; i <= n; i++) {
console.log("Hello world - your i input is: "+ i)
}
for(letj =1; j <= n; j++) {
console.log("Hello world - your j input is: "+ j)
}



很多小伙伴应该猜到了,就是* 2 n 次的复杂度,那就是 O(2n)**。其实还是 O(n) 的时间复杂度。



O(log(n))



for(leti =1; i < n; i = i *2) {
console.log("Hello world - your input is: "+ i);
}



O(k^n)



// Fibonacci递归
functionfib(n){
if(n <=2)returnn;
returnfib(n-1) + fib(n-2);
}





时间复杂度曲线



  • y 轴是 Operations 就是操作复杂度的指数;

  • x 轴是 Elements 就是 n 我们的循环次数 ;

  • 这里我们可以看到在 n 比较小的时候,复杂度是相对稳定的;

  • 但是当 n 越来越大时,Big-O复杂度就会急速飙升;



所以在我们写程序的时候,如果能把时间和空间复杂度从 O(n^2) 降到 O(n) 或者 O(1) 后,我们得到的优化收益是非常高的!



  • 在编写程序的时候一定要注意到它的时间和空间复杂度,这样编写的时候就能预测出这段代码的性能级别;

  • 用最简洁的时间和空间复杂度完成这段程序;

  • 这样就是最顶尖的职业编程选手了;

  • 因为复杂度越高,程序损耗的时间(处理时间)和资源(内存)就越大;



降低时间和空间复杂度



我们用个例子就可以看到如何在编程中降低复杂度:



计算:1 + 2 + 3 + … + n



方法一: 循环1到n然后累加 (时间复杂度 O(n) )



letsum =0
for(leti =1; i < n; i++) {
sum += i
}
console.log(sum)



方法二: 求和公式 sum = n(n+1)/2 (时间复杂度 O(1) )



letsum = n * (n +1) /2
console.log(sum)



注意:

1. 在做题或者面试的时候先 确认题目 ,确保一切的条件和题目的理解无误;

2. 想出所有可能 的解决方案;

3. 同时 比较每个方法 的时间和空间复杂度;

4. 接下来 找出最优 的解决方案(时间最快,内存使用最少)



判断时间和空间复杂度



斐波那契(Fibonacci)例子



公式:F(n) = F(n – 1) + F(n – 2)



我们可以直接使用递归来解题:



functionfib(n){
if(n <=2)returnn
returnfib(n -1) + fib(n -2)
}



  • 这个 fib 斐波那契函数中是一个 递归

  • 每一次传入一个 n 值时,都会循环递归 fib 方法来一层一层往下计算;

  • 最后到达 n 小于2,返回最后的 n 值;



那针对这个递归,我们怎么计算它的时间复杂度呢?



  • 要推断出这个程序的 复杂度 ,首先我们要知道具体在这个函数中程序做了什么;

  • 我们距离现在传入 n 6 ,那就是运行 fib(6)

  • 这个时候 6 被传入这个方法,然后返回的就是 fib(5) + fib(4) ,这时 fib(5) fib(4) 就会再进入 fib 函数,这里就分开了两个分支了。以此类推我们就会出现以下一个树状过程:





  • 通过上图展开来的树,我们可以看到每一层是上一层的2倍: fib(6) 展开为 fib(5) + fib(4) ,然后 fib(5) fib(4) 又展开了两个。

  • 所以 fibonacci 的执行次数就是一个 指数级 - O(2^n)

  • 这里我们也可以看到 fib(3) fib(4) 等等,都被重复计算了多次,所以这个计算的 复杂度高达2的6次方

  • 所以在做题和面试的时候就 不要运用上面的代码实例 ,我们要加入缓存机制, 缓存重复计算的结果 或者用 一个循环来写 ,从而降低这个程序的复杂度。





主定理 Master Theorem



任何一个 分治 或者* 递归函数 *都可以通过这个定理来算出它们的 时间复杂度 。这个定理里面有4种最常用的,只要记住这4种就可以了。





常见面试题



  • 二叉树遍历中的前序、中序、后序:时间复杂度是多少?

+ 时间复杂度是 O(n) ,无论是前序、中序或者后序每一个节点都会访问一次,并且仅访问一次;

+ 所以就是二叉树的节点总数,也就是 O(n) 的线性时间复杂度;

  • 图的遍历:时间复杂度是多少?

+ 时间复杂也是 O(n) , 这里的 n 就是图里面的节点总数;

  • 搜索算法:DFS、BFS时间复杂度是多少?

+ DFS是深度优先,BFS是广度优先算法。

+ 不管是深度优先还是广度优先,因为访问的节点只访问一次,所以时间复杂度也是 O(n) 的。( n 指的是搜索空间里面的节点总数)

  • 二分查找:时间复杂度是多少?

+ 答案是 O(log n)





总结



  • 程序复杂度:Big O Notation

  • O (1) ,* O(log n) *, O(n) ,* O(n^2) *, … 等等,越复杂程序性能越差;

  • 分析复杂度法则:分析代码的逻辑,找到程序中运行的次数;

  • 降低程序时间和空间复杂度可以提升代码的质量,同时优化程序的性能;

  • 主定理:

  • 所有的 分治 或者* 递归函数 *都可以通过 主定理 来分析出它的 时间复杂度

  • 常见面试题:

  • 二叉树遍历中的前序、中序、后序:时间复杂度是多少? O(n)

  • 图的遍历:时间复杂度是多少? O(n)

  • 搜索算法:DFS、BFS时间复杂度是多少? O(n)

  • 二分查找:时间复杂度是多少? O(log n)



我是 三钻 ,一个在 技术银河 中等你们一起来终身漂泊学习。

点赞是力量,关注是认可,评论是关爱!下期再见 :wave:!



公众号《 技术银河 》回复”算法资料”,可以获得这个系列文章的 PDF版 其他资料



InfoQ
我还没有学会写个人说明!
上一篇

《心灵奇旅》拿下豆瓣9.2分成年度开局最高片

下一篇

手把手教你做挖矿应急响应

你也可能喜欢

评论已经被关闭。

插入图片