我们常说的算法时间复杂度和空间复杂度到底是什么？

iShot2021-06-30 20.45.18

前言

针对某一类问题的解决，我们可能需要借助算法来实现，实现的手段也可能是各式各样的。虽然最终都解决了问题，但是各个解决手段，也就是算法还是存在优劣之分的。

既然存在比较，那肯定就有一个标准供来参考，那么我们在评价一个算法的优劣时参考的标准是什么呢？

算法的优劣主要从它执行时所占用的「时间」和「空间」两个方面来进行评定，也就是我们常听到的「时间复杂度」和「空间复杂度」。

谈到是时间复杂度，我们很多人的第一反应就是将算法执行一遍，打印出其执行的时间就是它所消耗的时间，其实这样是不可行的，因为：

实际场景中，我们更喜欢用一个估值来表示算法所编程序的运行时间。所谓估值，即估计的、并不准确的值。注意，虽然估值无法准确的表示算法所编程序的运行时间，但它的得来并非凭空揣测，需要经过缜密的计算后才能得出。

表示一个算法所编程序运行时间的多少，用的并不是准确值（事实上也无法得出），而是根据合理方法得到的预估值。

我们一般用“大 O 符号表示法”来表示时间复杂度：T(n) = O(f(n))

这个公式的全称是：算法的渐进时间复杂度。

大 O 符号表示法并不是用于来真实代表算法的执行时间的，它是用来表示代码执行时间的增长变化趋势的。

我们来看一个常见的例子：

for(let index = 0; index < n; index++){
    console.log(index);
}

可以看到，这段程序中仅有 2 行代码，其中：

因此，整段代码中所有语句共执行了 (n+1)+n 次，即 2n+1 次。数据结构中，每条语句的执行次数，又被称为该语句的频度。整段代码的总执行次数，即整段代码的频度。

这里仅介绍了以最坏情况下的频度作为时间复杂度，而在某些实际场景中，还可以用最好情况下的频度和最坏情况下的频度的平均值来作为算法的时间复杂度。

和时间复杂度类似，一个算法的空间复杂度，也常用大 O 记法表示。空间复杂度比较常用的有：

要知道每一个算法所编写的程序，运行过程中都需要占用大小不等的存储空间，例如：

首先，程序自身所占用的存储空间取决于其包含的代码量，如果要压缩这部分存储空间，就要求我们在实现功能的同时，尽可能编写足够短的代码。

程序运行过程中输入输出的数据，往往由要解决的问题而定，即便所用算法不同，程序输入输出所占用的存储空间也是相近的。

事实上，对算法的空间复杂度影响最大的，往往是程序运行过程中所申请的临时存储空间。不同的算法所编写出的程序，其运行时申请的临时存储空间通常会有较大不同。

如果程序所占用的存储空间和输入值无关，则该程序的空间复杂度就为 O(1)；反之，如果有关，则需要进一步判断它们之间的关系：

比如：

let m = 0;
for(let index = 0; index < 9999; index++){
    m++;
}

虽然 m 的值随着 index 的增加在一直变化，可是并未产生新的变量，即程序所占用的空间并未发生变化，所以，它的空间复杂度为 O(1)。

~ 本文完，感谢阅读！

学习有趣的知识，结识有趣的朋友，塑造有趣的灵魂！
大家好，我是〖编程三昧〗的作者 隐逸王，我的公众号是『编程三昧』，欢迎关注，希望大家多多指教！
你来，怀揣期望，我有墨香相迎！你归，无论得失，唯以余韵相赠！
知识与技能并重，内力和外功兼修，理论和实践两手都要抓、两手都要硬！

自由职业者, 工作空间, Coworking, 办公桌, 办公室, 计算机, 技术, 财经, 市场营销, 工作