算法复杂度分析 上

Question

什么是算法复杂度？

我们都知道，数据结构和算法本身是为了解决 快 和 省 的问题，即如何让代码运行更快，如何让代码更省内存空间，成了衡量一个算法执行效率的两个重要标准，简称就是 时间复杂度 和 空间复杂度 。

为什么需要复杂度分析？

传统的性能测试（事后统计法），就是把代码跑一遍，通过统计、监控，得到算法执行的时间和占用的内存，但是这种测试非常依赖测试坏境，并且测试结果受数据规模的影响很大。

相反，复杂度分析不依赖执行环境，就可以粗略的估算出算法的执行效率，成本小，易操作，指导性强，如果掌握了复杂度分析，往往能编写出性能更优的代码，有利于降低系统开发和维护成本。

大 O 复杂度表示法

算法的执行效率，粗略的讲，就是算法的执行时间。但是，如何在不运行代码的情况下，用“肉眼”就能看出一段代码的执行时间呢？

这里有一段非常简单的代码，求 1,2,3…n 的累加和，我们来尝试估算下该代码的执行时间。

function cal(n) {
    let sum = 0;
    let i = 1;
    for(; i <= n; i++) {
        sum += i;
    }
    return sum;
}

我们假设每行代码的执行时间都是一样的，为 unit_time，那么第 2、3 行代码分别需要 1 个 unit_time 的执行时间，第 4 、 5 行代码分别运行了 n 遍，因此需要 2n * unit_time 的执行时间，所以这段代码总的执行时间为 (2n+2) * unit_time。可以看出来，所有代码的执行时间 T(n) 与每行代码的执行次数成正比。

按照这个思路，我们再分析一段代码。

function cal(n) {
    let sum = 0;
    let i = 1;
    for(; i <= n; i++) {
        let j = 1;
        for(; j <= n; j++) {
            sum += i * j;
        }   
    }
    return sum;
}

第 2、3 行代码，每行都需要 1 个 unit_time 的执行时间，第 4、5 行代码循环执行了 n 遍，需要 2n * unit_time 的执行时间，第 6、7 行代码循环执行了 n2 次，所以需要 2$n^{2}$ * unit_time 的执行时间，所以，整段代码的执行时间 T(n) = (2n + 2$n^{2}$ + 2) * unit_time。

尽管我们不知道 unit_time 的具体值，但是通过这两段代码执行时间的推导过程，我们可以得到， 所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比 。

我们把这个规律总结成一个公式，那就是 大 O 表示法 ：

其中，T(n) 表示代码执行的时间，n 表示数据规模的大小，f(n) 表示每行代码的执行次数总和，公式中的 O，表示代码中的执行时间 T(n) 和 f(n) 成正比。

所以第一个例子中的 T(n) = O(2n + 2)，第二个例子中的 T(n) = O(2n + 2$n^{2}$ + 2)，就是 大 O 时间复杂度表示法 。

大 O 时间复杂度实际上并不代表代码真正的执行时间，而是代表 代码执行时间随数据规模增长的变化趋势 ，简称 时间复杂度 。

当 n 很大时，你可以把它想象成 10000、100000。而公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略。我们只需要记录一个最大量级就可以了，如果用大 O 表示法表示刚讲的那两段代码的时间复杂度，就可以记为：T(n) = O(n)； T(n) = O(n)。

时间复杂度分析

1. 只关注循环次数最多的一段代码

大 O 这种复杂度表示方法只是表示一种变化趋势。我们通常会忽略掉公式中的常量、低阶、系数，只需要记录一个最大阶的量级就可以了。所以，我们在分析一个算法、一段代码的时间复杂度的时候，也只关注循环执行次数最多的那一段代码就可以了。这段核心代码执行次数的 n 的量级，就是整段要分析代码的时间复杂度。

还是那之前的例子来说。

function cal(n) {
    let sum = 0;
    let i = 1;
    for(; i <= n; i++) {
        sum += i;
    }
    return sum;
}

其中第 2、3 行代码都是常量级的执行时间，与 n 的大小无关，所以对于复杂度并没有影响。循环执行次数最多的是第 4、5 行代码，所以这块代码要重点分析。前面我们也讲过，这两行代码被执行了 n 次，所以总的时间复杂度就是 O(n)。

2. 加法法则：总复杂度等于量级最大的那段代码的复杂度

我们先来看一段代码。

function cal(n) {
    let sum1 = 0;
    let sum2 = 0;
    let sum3 = 0;
    // 第一部分
    for(let i = 1; i <= 100; i++) {
        sum1 += i;
    }
    // 第二部分
    for(let i = i; i <= n; i++) {
        sum2 += i
    }
    // 第三部分
    for(let i = 1; i <= n; i++) {
        for(let j = 1; j <= n; j++) {
            sum3 = sum3 + i + j;
        }
    }

    return sum1 + sum2 + sum3;
}

这个代码分为三部分，分别是求 sum_1、sum_2、sum_3。我们可以分别分析每一部分的时间复杂度，然后把它们放到一块儿，再取一个量级最大的作为整段代码的复杂度。

第一段的时间复杂度是多少呢？这段代码循环执行了 100 次，所以是一个常量的执行时间，跟 n 的规模无关。

那第二段代码和第三段代码的时间复杂度是多少呢？答案是 O(n) 和 O(n2)。

综合这三段代码的时间复杂度，我们取其中最大的量级。所以，整段代码的时间复杂度就为 O(n2)，也就是说， 总的时间复杂度就等于量级最大的那段代码的时间复杂度 ，抽象成公式就是：

如果 T1(n)=O(f(n))，T2(n)=O(g(n))；那么 T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n)))=O(max(f(n), g(n))).

3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

我们根据加法法则来推导出乘法法则的计算公式，如果 T1(n) = O(f(n))，T2(n) = O(g(n))，那么 T(n) = T1(n) * T2(n) = O(f(n)) * O(g(n)) = O(f(n) * g(n))。

function cal(n) {
    let sum = 0;
    for(let i = 1; i <= n; i++) {
        sum += f(i)
    }
}

function f(n) {
    let sum = 0;
    for(let i = 1; i <= n; i++) {
        sum += i;
    }
    return sum;
}

单独函数 cal 的时间复杂度为 T1(n) = O(n)，单独函数 f 的时间复杂度为 T2(n) = O(n)，所以，整个函数 cal 的时间复杂度就是，T(n) = T1(n) * T2(n) = O(n*n) = O(n2)。