复杂度分析
数据结构和算法本身解决的是 代码执行速度快 和 节省占用的内存 的问题，那么如何衡量你写的算法的执行效率呢？这里我们就要用到 复杂度分析：时间 和 空间 复杂度分析。
复杂度分析 是整个算法学习的精髓，是我们必须要掌握的，只要掌握了它，数据结构和算法的内容基本上就掌握了一半。
为什么需要复杂度分析
我们能够通过统计、监控，就能得到算法执行的时间和占用的内存大小， 那么我们 为什么 需要做 复杂度分析。首先这前面这种通过统计监控的方法，我们称之为 事后统计法。但是 这种 统计方法 有很大的局限性。 其表现在 两个方面：
1. 测试结果非常依赖测试环境， 比如测试环境的 硬件配置；
2.测试结果受数据规模的影响很大，比如测试数据规模太小，测试结果可能无法真实的反应算法的性能。
所以，我们需要一个不用具体的测试数据来测试，就可以粗略地估计算法的执行效率的方法。这就是 时间、空间复杂度分析方法。
如何运用复杂度分析：大O表示法
大O表示法仅仅是一种粗略的分析模型，是一种估算，能帮助我们短时间内了解一个算法的执行效率。
如上图代码，假设我们设定每行代码执行的时间是 相同 的，都是单位时间 time, 那么上面的代码执行了多少个 单位时间呢？
首先，第一行和第二行代码都执行了 1遍，所以是 1 + 1 = 2 time; 而第三行 和 第四行 执行了 length 遍 ，length = n， 所以这两行都 执行了 n time， n + n = 2n time。
所以，这段代码可以 粗略的得到 运行的总时间 (2n + 2) time, 所以 代码的执行时间T(n) 和 每行代码的执行次数成 正比。
再来看一段代码
通过这两段代码执行时间的推导过程，我们可以看到，所有代码的执行时间T(n)与每行代码 的执行次数n成正比。
我们可以将这个规律总结成一个公式，这就是我们所说的 大O表示法。
T(n) = O(f(n))
T(n) 表示代码执行的时间；n 表示数据规模的大小；f(n)表示每行代码执行的次数总时间。因为这是一个公式，所以用f(n)来表示。公式中的O，表示代码的执行时间T(n)与f(n)表达式成正比。
上述的第一段代码 可以 表示为 T(n) = O(2n + 2), 第二段 可以表示为 T(n) = O(2n^2+2n+2)。这就是 大O时间复杂度表示法。大O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。
当n很大时，你可以把它想象成10000、100000 甚至 无穷大。而公式中的低阶、常量、系数三部分并不左右增长趋势，所以都 可以忽略。我们只需要记录一个 最大量级 就可以 了，如果用大O表示法表示刚讲的那两段代码的时间复杂度，就可以记为：T(n) = O(n)； T(n) = O(n^2)。
时间复杂度如何分析
1.只关注循环执行次数最多的一段代码
如上图的代码1， 当 n 无穷大的时候， 低阶、常量、系数可以忽略不计，我们只用关心这个 for 循环就可以了， 所以它的时间复杂度 就是 O(n)。
2.加法法则：总复杂度 等于 量级最大 的那段代码的复杂度
我们分析这段 代码， 它的 时间复杂度 是 (2 + 2n + 2n^2) time， 当 n 是无穷大的时候， 我们取起中量级最大的， n^2, 所以 这段代码的 时间复杂度 就是 O(n^2)。
总结 : 总的时间复杂度就等于量级最大的那段代码的时间 复杂度。
3.乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
理解了 加法法则，那么乘法法则就不难理解。
上面代码 fun2 调用了 fun，fun2 的时间复杂度 就是 T1(n) * T2(n^2) = O(n) * O(n^2) = O(n^3)。
总结：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。
常见的时间复杂度
常见的复杂度量级有：常量阶（O(1)）、对数阶（O(logn)）、线性阶（O(n)）、线性对数阶（O(nlogn)）、平方、立方、k次方阶（O(n^2)、O(n^3).........O(n^k)）、指数阶（O(2^n)）、阶乘阶（O(n!)）。
上述复杂度量阶可以 粗略的 分为两类：多项式量级 和 非多项式量级。其中，非多项式量级只有两个：O(2^n) 和 O(n!)。 当 n 越来越大时，非多项式量级就是 急剧的 增大， 执行的时间就会 无限增长，因此，非多项式量级 是 效率很低的算法。
O(1)
O(1) 表示的 不是 执行了一行代码，是 常量级 时间复杂度的一种表示方法， 比如
虽然代码有三行，但是 它的时间复杂度 也是 O(1)，只要代码的执行时间不随 n 的增大而增长，这样代码的时间复杂度我们都记作 O(1)。或者说，一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是 Ο(1)。
O(logn)、O(nlogn)
对数阶时间复杂度： 计算出上述代码的执行次数，我们就能得到它的时间复杂度，那么我们要如何计算呢。运用高中的知识：
2^0 * 2^1 * 2^2 *........2^x = n;
x 就等于 log2(n), 所以它的时间复杂度就是 是 O(log2(n))， 采用大 O 表示法 我们可以忽略掉系数，所以不论是 log3(n), 还是 log4(n)...... 它们的时间复杂度可以 统一的为 O(logn），那么 O(nlogn) 是 如何出现的，我们可以参考 上面的 乘法法则，如果一段代码的时间复杂度是O(logn)，我们循环执行 n 遍，时间复杂度就是 O(nlogn) 了。
空间复杂度分析
空间复杂度全称 就是 渐进空间复杂度（asymptotic space complexity），表示算法的存储空间（额外的内存消耗）与数据规模之间的增长关系。
如当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)；当一个算法的空间复杂度与 n 成线性比例关系时，可表示为 O(n)
我们常见的空间复杂度就是O(1)、O(n)、O(n^2 )，空间复杂度 比 时间复杂度 简单一些。
