共计 2115 个字符，预计需要花费 6 分钟才能阅读完成。
前言
针对某一类问题的解决，咱们可能须要借助算法来实现，实现的伎俩也可能是各式各样的。尽管最终都解决了问题，然而各个解决伎俩，也就是算法还是存在优劣之分的。
既然存在比拟，那必定就有一个规范供来参考，那么咱们在评估一个算法的优劣时参考的规范是什么呢？
算法的优劣次要从它执行时所占用的「工夫」和「空间」两个方面来进行评定，也就是咱们常听到的「工夫复杂度」和「空间复杂度」。
- 工夫复杂度：执行算法所须要的计算工作量，能够估算出程序对处理器的应用水平。
- 空间复杂度：执行以后算法所须要的内存空间，能够估算出程序对处理器的应用水平。
工夫复杂度
谈到是工夫复杂度，咱们很多人的第一反馈就是将算法执行一遍，打印出其执行的工夫就是它所耗费的工夫，其实这样是不可行的，因为：
- 解决一个问题的算法可能有很多种，一一实现的工作量无疑是微小的，得失相当；
- 不同计算机的软、硬件环境不同，即使应用同一台计算机，不同时间段其零碎环境也不雷同，程序的运行工夫很可能会受影响，重大时甚至会导致误判。
理论场景中，咱们更喜爱用一个估值来示意算法所编程序的运行工夫。所谓估值，即预计的、并不精确的值。留神，尽管估值无奈精确的示意算法所编程序的运行工夫，但它的得来并非凭空推测，须要通过周密的计算后能力得出。
示意一个算法所编程序运行工夫的多少，用的并不是精确值（事实上也无奈得出），而是依据正当办法失去的预估值。
咱们个别用“ 大 O 符号表示法 ”来示意工夫复杂度：T(n) = O(f(n))
- n 是影响复杂度变动的因子
- f(n) 是复杂度具体的算法
- O 示意正比例关系
这个公式的全称是： 算法的渐进工夫复杂度 。
大 O 符号表示法并不是用于来实在代表算法的执行工夫的，它是用来示意代码执行工夫的增长变化趋势的。
咱们来看一个常见的例子：
for(let index = 0; index < n; index++){console.log(index);
}能够看到，这段程序中仅有 2 行代码，其中：
- for 循环从 index 的值为 0 始终逐增至 n（留神，循环退出的时候 index 值为 n），因而 for 循环语句执行了 n+1 次；
- 而循环外部仅有一条语句，index 的值每增 1 该语句就执行一次，始终到 index 的值为 n-1，因而，打印语句一共执行了 n 次。
因而，整段代码中所有语句共执行了 (n+1)+n 次，即 2n+1 次。数据结构中，每条语句的执行次数，又被称为该语句的频度。整段代码的总执行次数，即整段代码的频度。
常见的工夫复杂度量级
- 常数阶 O(1)
- 对数阶 O(logN)
- 线性阶 O(n)
- 平方阶 O(n^2)
- 立方阶 O(n^3)
- K 次方阶 O(n^k)
- 指数阶 (2^n)
这里仅介绍了以最坏状况下的频度作为工夫复杂度，而在某些理论场景中，还能够用最好状况下的频度和最坏状况下的频度的平均值来作为算法的工夫复杂度。
空间复杂度
和工夫复杂度相似，一个算法的空间复杂度，也罕用大 O 记法示意。空间复杂度比拟罕用的有：
- O(1)
- O(n)
- O(n²)
要晓得每一个算法所编写的程序，运行过程中都须要占用大小不等的存储空间，例如：
- 程序代码自身所占用的存储空间；
- 程序中如果须要输入输出数据，也会占用肯定的存储空间；
- 程序在运行过程中，可能还须要长期申请更多的存储空间。
首先，程序本身所占用的存储空间取决于其蕴含的代码量，如果要压缩这部分存储空间，就要求咱们在实现性能的同时，尽可能编写足够短的代码。
程序运行过程中输入输出的数据，往往由要解决的问题而定，即使所用算法不同，程序输入输出所占用的存储空间也是相近的。
事实上，对算法的空间复杂度影响最大的，往往是程序运行过程中所申请的长期存储空间。不同的算法所编写出的程序，其运行时申请的长期存储空间通常会有较大不同。
如果程序所占用的存储空间和输出值无关，则该程序的空间复杂度就为 O(1)；反之，如果无关，则须要进一步判断它们之间的关系：
- 如果随着输出值 n 的增大，程序申请的长期空间成线性增长，则程序的空间复杂度用 O(n) 示意;
- 如果随着输出值 n 的增大，程序申请的长期空间成 n2 关系增长，则程序的空间复杂度用 O(n2) 示意；
- 如果随着输出值 n 的增大，程序申请的长期空间成 n3 关系增长，则程序的空间复杂度用 O(n3) 示意；
比方：
let m = 0;
for(let index = 0; index < 9999; index++){m++;}尽管 m 的值随着 index 的减少在始终变动，可是并未产生新的变量，即程序所占用的空间并未发生变化，所以，它的空间复杂度为 O(1)。
总结
- 工夫复杂度和空间复杂度都是一种通过谨严推算得出的预估值，并不能代表理论状况。
- 工夫复杂度和空间复杂度代表的是一种趋势。
- 咱们个别状况下所说的工夫复杂度和空间复杂度，都是最坏状况下的执行趋势，理论状况可能比预估的要好。
- 少数业务场景下，一个好的算法往往更重视的是工夫复杂度的比拟，而空间复杂度只有在一个正当的范畴内就能够。
~
~ 本文完，感激浏览！
~
学习乏味的常识，结识乏味的敌人，塑造乏味的灵魂！
大家好，我是〖编程三昧〗的作者 隐逸王 ，我的公众号是『编程三昧』，欢送关注，心愿大家多多指教！
你来，怀揣冀望，我有墨香相迎！你归，无论得失，唯以余韵相赠！
常识与技能并重，内力和外功兼修，实践和实际两手都要抓、两手都要硬！
