算法复杂度分析 中

Question

几种常见的时间复杂度案例分析

复杂度量级，可以粗略的分为两类： 多项式量级 和 非多式量级 。其中，非多项式量级只有两个：$O(2^{n})$ 和 O(n!)。

当数据规模 n 越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的时间会无限增长。所以，非多项式量级算法是非常低效的，这里我们就不多陈述了。我们主要看下几种常见的多项式量级的时间复杂度。

1. O(1)

O(1) 只是一种常见的常量时间复杂度，并不是说只执行了一行代码。比如这段代码，即便有 3 行，它的时间复杂度也是 O(1)，而不是 O(3)。

let i = 0;
let j = 0;
let sum = i + j;

总结来说，只要代码的执行时间不随 n 的增大而增长，这样的代码的时间复杂度我们都计作 O(1)，或者说，
一般情况下，只要算法中不存在循环语句、递归语句，即便有成千上万行代码，其时间复杂度也是 O(1) 。

2. O(logn)、O(nlogn)

对数阶算法复杂度很常见，同时它也是最难分析的一种时间复杂度。举个例子说明一下。

let i = 1;
while(i <= n) {
  i = i * 2;
}

根据前面的时间复杂度分析方法，第三行代码是循环次数最多的。所以，我们只要计算出这行代码被执行了多少次，就能知道整段代码的时间复杂度。

从代码中可以看出，变量 i 的值从 1 开始取，每循环一次就乘以 2。当大于 n 时，循环结束。还记得我们高中学过的等比数列吗？实际上，变量 i 的取值就是一个等比数列。如果我把它一个一个列出来，就应该是这个样子的：

所以，我们只要知道 x 值是多少，就知道这行代码执行的次数了。通过 2x=n 求解 x 值我就不多说了，$x=log_2 n$，所以，这段代码的时间复杂度为 O(log2n)。

再稍微修改下代码。

let i = 1;
while(i <= n) {
  i = i * 3;
}

根据之前的思路，我们很简单就可以推算出来，这段代码的时间复杂度为 O(log3n)。

实际上，不管是以 2 为底、以 3 为底，还是以 10 为底，我们可以把所有的对数时间复杂度都计为 O(logn)。为什么呢？

我们知道，对数之间是可以互相转换的，$log_3 n = log_3 2 * log_2 n$，所以 log3n=O(C∗log2n)，其中 C=log32 是一个常量，基于我们前面的理论： 在使用大 O 复杂度表示法的时候，可以忽略常量、低阶、系数，即 O(Cf(n)) = O(f(n)) 。所以，$O(log_3 n)$ 就等于 O(log2n)。因此，在对数阶时间复杂度中，我们可以忽略对数“底”的存在，统一表示为 O(logn)。

说到这里，那 O(nlogn) 也就很好理解了吧，还记得我们上篇文章中说的 乘法法则 吗？如果一段代码的时间复杂度为 O(logn)，我们循环了 n 变，时间复杂度就变成了 O(nlogn)。

O(nlogn) 是一种非常常见的时间复杂度。比如，归并排序、快速排序的时间复杂度都是 O(nlogn)。

3. O(m+n)、O(m*n)

我们再来讲一种跟前面都不一样的时间复杂度，代码的复杂度 由两个数据的规模 来决定。老规矩，先看代码！

function cal(m, n) {
    let sum1 = 0;
    let sum2 = 0;
    for(let i = 1; i <= m; i++) {
        sum1 += 1;
    }
    for(let i = 1; i <= n; i++) {
        sum2 += 1;
    }
    return sum1 + sum2;
}

从代码中可以看出，m 和 n 是表示两个数据规模。我们无法事先评估 m 和 n 谁的量级大，所以我们在表示复杂度的时候，就不能简单地利用加法法则，省略掉其中一个。所以，上面代码的时间复杂度就是 O(m+n)。

针对这种情况，原来的加法法则就不正确了，我们需要将加法规则改为：T1(m) + T2(n) = O(f(m) + g(n))。但是乘法法则继续有效：T1(m)*T2(n) = O(f(m) * f(n))。

空间复杂度

我们再来回顾一下，时间复杂度的全程为 渐进时间复杂度，表示算法执行时间与数据规模之间的增长关系 。类比一下，空间复杂度全程就是 渐进空间复杂度，表示算法存储空间与数据规模之间的增长关系 。

function print(n) {
    let a = [];
    for(let i = 0; i < n; i++) {
        a[i] = i * i;
    }
    for(let i = n - 1; i >=0; i--) {
        console.log(a[i]);
    }
}

在上述代码中，我们申请了一个空间存储变量 i，但是它是常量阶的，跟数据规模 n 没有关系，所以忽略。之后又申请了一个大小为 n 的数组，除此之外，剩下的代码没有占用更多的存储空间。所以，这段代码的空间复杂度就是 O(n)。

我们常见的空间复杂度就是 O(1)、$O(n)$、$O(n)$，像 O(logn)、$O(nlogn)$ 这样的对数阶复杂度平时都用不到。而且，空间复杂度分析比时间复杂度分析要简单很多。所以，对于空间复杂度，掌握刚我说的这些内容已经足够了。

小结

复杂度也叫渐进复杂度，包括时间复杂度和空间复杂度，用来分析算法执行效率与数据规模之间的增长关系，可以粗略地表示，越高阶复杂度的算法，执行效率越低。常见的复杂度并不多，从低阶到高阶有：$O(1)$、$O(logn)$、$O(n)$、$O(nlogn)$、$O(n^{2})$。