【数据结构与算法】分析时间复杂度与空间复杂度
source link: https://xie.infoq.cn/article/770c42cd2364b5ce792f1a25c
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
本文是覃超老师的《算法训练营》的学习笔记，此笔记的内容包含了学习后的个人记录、个人总结、理解和思想。从而更好的学习算法。
前言
学习任何一门知识的时候，我们需要分析清楚这门知识的核心是什么，从而在这个核心中我们可以得到什么。如果我们是盲目的吸收知识，其实很多知识我们都是在目前场景、工作、生活中无法使用的。也是因为学习之后无法运用，所以我们很快就会遗忘，或者是在学习的过程中很容易就会放弃。
在一生的学习的过程中，发现学习我们急需使用或者能给我们及时带来价值的知识，我们会学的更加牢固，更加能坚持学习。
学习《数据结构与算法》这门知识的核心是什么？又能得到什么呢？
-
弄懂编程的底层逻辑；
-
在编程的过程中，拥有一个哆啦A梦一样百宝工具袋；
-
在遇到性能问题的时候，有算法的思维逻辑和规则来解决问题；
-
提高编程思维；
这篇笔记记录了算法的核心 时间和空间复杂度 ，《数据结构与算法》都是围绕着这个核心开展的。它的存在也是为了解决我们在编程的过程中性能问题，同时也让我们有更高级的思维和思路，写出更优质的程序。
复杂度指标 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版 和 其他资料 ！
Recommend
-
50
点击蓝色“ 乔志勇笔记 ”关注我哟 加个“ 星标 ”，第一时间获取推送...
-
42
1. 博客背景 今天有同事在检查代码的时候，由于函数写的性能不是很好，被打回去重构了，细思极恐，今天和大家分享一篇用js讲解的时间复杂度和空间复杂度的博客 2. 复杂度的表示方式 之前有看过的，你可能...
-
20
目录 一、时间复杂度：执行算法所需要的计算工作量 （一）时间复杂度的理解 2.（渐进）时间复杂度定义 （二）时间复杂度的计算
-
25
复杂度分析 复杂度是算法里面最重要的概念，算法的差别就是复杂度分析。 实际的应用场景，一个算法O(n)的，可能比O(1)更快，但是当n非常大的时候，比如服务端上千万的用户，不同的算法产生的效率差别非常大。
-
9
各种排序算法时间复杂度和空间复杂度表 各种排序算法时间复杂度和空间复杂度表: 各种排序算法时间复杂度和空间复杂度表 比较时间复杂度函数的情况如下图： 比较时间复杂度函数的情况...
-
13
关注公众号「五分钟学算法」，回复关键字 算法，获取谷歌工程师的 LeetCode 算法笔记。...
-
5
针对某一类问题的解决，我们可能需要借助算法来实现，实现的手段也可能是各式各样的。虽然最终都解决了问...
-
5
作为一名“程序猿”，大家应该都听过这么一句话：程序=数据结构+算法。 这句话是由瑞士计算机科学家尼古拉斯·沃斯（Niklaus Wirth）在 1984 年获得图灵奖时说的一句话，这位大佬还以这句话为名出了一本书《Algorithms + Data Structures=Programs》，从此...
-
2
目录1、算法的复杂度2、时间复杂度3、常见时间复杂度计算举例1、算法的复杂度算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏，一般...
-
4
算法的时间、空间复杂度如何比较？ 精选 原创 一、时间复杂度BigO
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK