复杂度分析是整个算法学习的精髓，只要掌握了它，数据结构和算法的内容基本上就掌握了一半了。
1. 什么是复杂度分析 ？数据结构和算法解决是 “如何让计算机更快时间、更省空间的解决问题”。
因此需从执行时间和占用空间两个维度来评估数据结构和算法的性能。
分别用时间复杂度和空间复杂度两个概念来描述性能问题，二者统称为复杂度。
复杂度描述的是算法执行时间（或占用空间）与数据规模的增长关系。
2. 为什么要进行复杂度分析 ？和性能测试相比，复杂度分析有不依赖执行环境、成本低、效率高、易操作、指导性强的特点。
掌握复杂度分析，将能编写出性能更优的代码，有利于降低系统开发和维护成本。
3. 如何进行复杂度分析 ？ 3.1 大 O 表示法算法的执行时间与每行代码的执行次数成正比，用 T(n) = O(f(n)) 表示，其中 T(n) 表示算法执行总时间，f(n) 表示每行代码执行总次数，而 n 往往表示数据的规模。这就是大 O 时间复杂度表示法。
3.2 时间复杂度1）定义
算法的时间复杂度，也就是算法的时间量度。
大 O 时间复杂度表示法 实际上并不具体表示代码真正的执行时间，而是表示 代码执行时间随数据规模增长的变化趋势，所以也叫 渐进时间复杂度，简称 时间复杂度（asymptotic time complexity）。
例子1：
function aFun() { console.log("Hello, World!"); // 需要执行 1 次 return 0; // 需要执行 1 次 }那么这个方法需要执行 2 次运算。
例子 2：
function bFun(n) { for(let i = 0; i < n; i++) { // 需要执行 (n + 1) 次 console.log("Hello, World!"); // 需要执行 n 次 } return 0; // 需要执行 1 次 }那么这个方法需要执行 ( n + 1 + n + 1 ) = 2n +2 次运算。
例子 3：
function cal(n) { let sum = 0; // 1 次 let i = 1; // 1 次 let j = 1; // 1 次 for (; i <= n; ++i) { // n 次 j = 1; // n 次 for (; j <= n; ++j) { // n * n ，也即是 n平方次 sum = sum + i * j; // n * n ，也即是 n平方次 } } }注意，这里是二层 for 循环，所以第二层执行的是 n * n = n2 次，而且这里的循环是 ++i，和例子 2 的是 i++，是不同的，是先加与后加的区别。
那么这个方法需要执行 ( n2 + n2 + n + n + 1 + 1 +1 ) = 2n2 +2n + 3 。
2）特点
以时间复杂度为例，由于 时间复杂度 描述的是算法执行时间与数据规模的 增长变化趋势，所以 常量、低阶、系数 实际上对这种增长趋势不产生决定性影响，所以在做时间复杂度分析时 忽略 这些项。
所以，上面例子1 的时间复杂度为 T(n) = O(1)，例子2 的时间复杂度为 T(n) = O(n)，例子3 的时间复杂度为 T(n) = O(n2)。
3.3 时间复杂度分析
只关注循环执行次数最多的一段代码
单段代码看高频：比如循环。
function cal(n) { let sum = 0; let i = 1; for (; i <= n; ++i) { sum = sum + i; } return sum; }执行次数最多的是 for 循环及里面的代码，执行了 n 次，所以时间复杂度为 O(n)。
加法法则：总复杂度等于量级最大的那段代码的复杂度
多段代码取最大：比如一段代码中有单循环和多重循环，那么取多重循环的复杂度。
function cal(n) { let sum_1 = 0; let p = 1; for (; p < 100; ++p) { sum_1 = sum_1 + p; } let sum_2 = 0; let q = 1; for (; q < n; ++q) { sum_2 = sum_2 + q; } let sum_3 = 0; let i = 1; let j = 1; for (; i <= n; ++i) { j = 1; for (; j <= n; ++j) { sum_3 = sum_3 + i * j; } } return sum_1 + sum_2 + sum_3; }上面代码分为三部分，分别求 sum_1、sum_2、sum_3 ，主要看循环部分。
第一部分，求 sum_1 ，明确知道执行了 100 次，而和 n 的规模无关，是个常量的执行时间，不能反映增长变化趋势，所以时间复杂度为 O(1)。
第二和第三部分，求 sum_2 和 sum_3 ，时间复杂度是和 n 的规模有关的，为别为 O(n) 和 O(n2)。
所以，取三段代码的最大量级，上面例子的最终的时间复杂度为 O(n2)。
同理类推，如果有 3 层 for 循环，那么时间复杂度为 O(n3)，4 层就是 O(n4)。
所以，总的时间复杂度就等于量级最大的那段代码的时间复杂度。
乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积