前端 算法的时间复杂度和空间复杂度

算法的评估

对于一个问题，经常有多种不同的求解算法，这时候我们就需要一个对算法进行评估的标准，找出最优的方案，评估一个算法有以下几个维度：

• 正确性：能正确的实现功能，满足问题的需求。
• 易读性：通常，写出一个利与人类阅读的代码和利于机器阅读的代码一样重要
• 健壮性：对于预料之外的输入，也能做出合适的处理。
• 时空性：算法的时间性能(算法的计算量)和空间性能(算法需要的存储量)、

时间复杂度

时间复杂度的计算方法

时间复杂度：在给定输入(问题规模)下，算法的计算量。

所以说，求一个算法的时间复杂度，就是求这个算法在给定问题规模下的计算量，那么问题来了：如何求算法的计算量？

算法计算量的求法规则如下：

• 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
}
}