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

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) 是高效的算法。对于合理大的 nO(n^3) 也是可以接受的。

空间复杂度

空间复杂度的计算方法

空间复杂度:给定输入(问题规模)下,算法运行时所占用的临时存储空间。

一个算法执行期间所占用的存储量分为三部分:

  • 算法本身的代码所占用的空间
  • 输入数据所占用的空间
  • 辅助变量所占用的空间

由于实现不同算法所需的代码不会有数量级的差别,所以算法本身代码所占用的空间我们可以不考虑

输入的数据所占用的空间是由问题决定的,与算法无关,所以我们也不需要考虑

我们需要考虑的只有一个:程序执行期间,辅助变量所占用的空间。

计算方法类似于计算算法的时间复杂度,空间复杂度我们用 S(n) 来表示,它同样是输入数据规模 n 的函数,用大 O 表示法记为:

S(n) = O(g(n))

其中 g(n) 是一个关于 n 的函数,如:g(n) = ng(n) = n^2g(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

相关推荐

bluewelkin / 0评论 2020-02-02