算法复杂度分析（上）

为什么需要算法复杂度分析？

首先，这和研究数据结构和算法的目的有关——“快”而“省”的解决问题。那么如何衡量算法的性能呢？就需要算法复杂度分析。

其次，除了算法复杂度分析，还有一种方法可以衡量复杂度，那就是“事后统计法”，即直接运行程序，统计需要的时间和空间。但是，这种方法有两个问题：

1）结果非常依赖于测试环境。比如，用 Core i3 和用 Core i8 运行程序所需的时间是不同的；

2）结果受测试规模的影响特别大。比如，对有序数组进行排序的时间比对逆序数组排序的时间短；对于小规模数据而言，插入排序所需时间比快速排序要短。

所以，就需要有一种不用具体测试数据，也能估计算法执行效率的方法，就是算法复杂度分析，包括时间、空间复杂度分析。

大 O 复杂度表示法

大 O 复杂度表示法可以归纳成下面一句话：

所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比。

即 T(n) = O(f(n))。其中，f(n) 表示代码的执行次数之和。大 O 符号（Big O notation）是用于描述函数渐进行为的数学符号，它代表“order of...”（...阶）。

例如，对于代码：

function foo (n) {
    var i = 0;
    var j = 0;
    for (; i < n; i++) {
        j += i;
    }
}

假设每行代码的执行时间一样，为 unit_time。则第 2、3 行执行时间均为 1 unit_time，第 4、5 行代码执行时间均为 n unit_time，整个函数的执行时间 T(n) = (2n + 2) * unit_time。用大 O 复杂度表示法表示即为 T(n) = O(2n + 2)。

注意，大 O 时间复杂度并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势。所以，它也叫渐进时间复杂度，简称时间复杂度。

当 n 很大时，不左右增长趋势的低阶、常量、系数均可忽略。所以，上面例子中的时间复杂度为 O(n)。

时间复杂度分析

时间复杂度分析有下面几个原则：

1）只关注循环执行次数最多的一段代码；

2）加法原则：总复杂度等于量级最大的那段代码的复杂度。用公式表示即为：T1(n) = O(f(m))，T2(n) = O(g(n))，T1(n) + T2(m) = O(max(f(n), g(m)))；

3）乘法原则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘机。用公式表示即为：T1(n) = O(f(m))，T2(n) = O(g(n))，T1(n) * T2(m) = O(f(n) * g(m))

常见的时间复杂度有以下几种：

1）常量阶：O(1)

2）对数阶：O(logn)

3）线性阶：O(n)

4）线性对数阶：O(nlogn)

5）平方阶：O(n ^ 2)

6）指数阶：O(2 ^ n)

7）阶乘阶：O(n!)

其中，1）-5）为多项式量级；6）、7）为非多项式量级，所对应的算法问题被称为非确定多项式问题（NP 问题，Non-Deterministic Polynomial）。

空间复杂度分析

空间复杂度全称为渐进空间复杂度（asymptostic space complexity）。空间复杂度较为简单，常见的空间复杂度为 O(1)，O(n) 和 O(n ^ 2)。

最后，用几种复杂度的坐标图作为结尾：

首发于微信公众号《代码写完了》