算法复杂度分析（上）
为什么需要算法复杂度分析？
首先，这和研究数据结构和算法的目的有关——“快”而“省”的解决问题。那么如何衡量算法的性能呢？就需要算法复杂度分析。
其次，除了算法复杂度分析，还有一种方法可以衡量复杂度，那就是“事后统计法”，即直接运行程序，统计需要的时间和空间。但是，这种方法有两个问题：
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。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)。
最后，用几种复杂度的坐标图作为结尾：
首发于微信公众号《代码写完了》
