前端 算法的时间复杂度和空间复杂度
jiayuqicz 2020-02-02
算法的评估
对于一个问题，经常有多种不同的求解算法，这时候我们就需要一个对算法进行评估的标准，找出最优的方案，评估一个算法有以下几个维度：
- 正确性：能正确的实现功能，满足问题的需求。
- 易读性：通常，写出一个利与人类阅读的代码和利于机器阅读的代码一样重要
- 健壮性：对于预料之外的输入，也能做出合适的处理。
- 时空性：算法的时间性能(算法的计算量)和空间性能(算法需要的存储量)、
时间复杂度
时间复杂度的计算方法
时间复杂度：在给定输入(问题规模)下，算法的计算量。
所以说，求一个算法的时间复杂度，就是求这个算法在给定问题规模下的计算量，那么问题来了：如何求算法的计算量？
算法计算量的求法规则如下：
- 1、在算法中选择几种“基本操作”，例如：赋值语句、数学运算语句等等。
- 2、给定输入下，计算算法执行了多少次“基本操作”。
- 3、“基本操作”的次数即可作为计算量。
实例与大O表示法
我们以一个例子来说明，求如下表达式的值：
// 阶乘的和 1! + 2! + 3! + ... + n!
我们可以写出如下程序(js代码)：
function factorial (n) {
var s = 0,
temp = 1
for (var i = 1; i <= n; i++) {
temp = 1
for (var j = 1; j <= i; j++) {
temp *= j
}
s += temp
}
return s
}我们根据之前总结的算法计算量的求法规则可知，求解一个算法的计算量分为三个步骤，第一步：确定基本操作，对于上面的代码我们所挑选的基本操作如下：
- 第一部分赋值语句：
var s = 0 temp = 1
当我们的输入规模即 n 变化时，这两条语句的执行次数没有变，始终是 2 次。
第二部分赋值语句：
for (var i = 1; i <= n; i++) { temp = 1 ... }第一层循环里的
temp = 1，该语句的执行次数等于输入规模n。乘法计算语句：
for (var j = 1; j <= i; j++) {
temp *= j
}第二层循环里的 temp *= j，该语句的执行次数，当 n = 1 时执行 1 次，当 n = 2 时执行 1 + 2 次，当 n = 3 时执行 1 + 2 + 3 次，所以该语句的执行次数与输入规模 n 的关系是 1 + 2 + 3 + ... + n = n(n + 1) / 2。
- 加法计算语句：
for (var i = 1; i <= n; i++) { ... s += temp }第一层循环里的加法赋值语句，该语句的执行次数等于输入规模n。
综上所述，根据我们选择的“基本操作”，可以计算出该算法的基本操作次数与输入规模 n 的关系如下：
T(n) = 2 + n + n(n + 1) / 2 + n = 1/2n^2 + 3/2n + 2
当 n 足够大时，n^2 起支配作用，使用 O(n^2) 表示 T(n) 的近似值，这种表示法成为 大 O 表示法。
常见的时间复杂度阶数
- 常熟阶 O(1)：即算法的计算量不随着输入规模的变化而变化。
- 线性阶 O(n)
- 多项式阶 O(n^c)：常见的多项式阶如 O(n^2)、O(n^3)
- 指数阶 O(C^n)：常见的指数阶如 O(2^n)
一般我们认为一个算法的时间复杂度为指数阶的时候，该算法是实际不可运算的，大家可以想象一下，如果一个算法的时间复杂度为 O(2^n) 当 n = 1000 时，这个数值是何等恐怖。更何况我们的输入规模 n 很可能远大于 1000。
另外我们认为时间复杂度为 O(n)、O(log2N)、O(n^2) 是高效的算法。对于合理大的 n，O(n^3) 也是可以接受的。
空间复杂度
空间复杂度的计算方法
空间复杂度：给定输入(问题规模)下，算法运行时所占用的临时存储空间。
一个算法执行期间所占用的存储量分为三部分：
- 算法本身的代码所占用的空间
- 输入数据所占用的空间
- 辅助变量所占用的空间
由于实现不同算法所需的代码不会有数量级的差别，所以算法本身代码所占用的空间我们可以不考虑
输入的数据所占用的空间是由问题决定的，与算法无关，所以我们也不需要考虑
我们需要考虑的只有一个：程序执行期间，辅助变量所占用的空间。
计算方法类似于计算算法的时间复杂度，空间复杂度我们用 S(n) 来表示，它同样是输入数据规模 n 的函数，用大 O 表示法记为：
S(n) = O(g(n))
其中 g(n) 是一个关于 n 的函数，如：g(n) = n、g(n) = n^2、g(n) = log2N 等等。
实例
假设我们有一个数组，该数组有100个元素，写一个转置该数组的算法：
function reverse (arr) {
for (var i = 0; i <= arr.length / 2 - 1; i++) {
var temp = arr[i]
arr[i] = arr[arr.length - i - 1]
arr[arr.length - i - 1] = temp
}
}上面的算法中，我们采用中间变量 temp 对数组的值进行逐个对应的首尾交换，最终达到转置的目的，我们可以看到，辅助变量只有一个即 temp，该变量存储一个数字类型的值，temp 所占用的内存不会随输入数组规模的增大而增大，所以上面算法的控件复杂度为 O(1)，是常数阶，即上面算法的空间复杂度 S(n) = O(1)。
from: http://blog.poetries.top/js-knowledge-note/#/note/algorithm/time-space
