复杂度分析

时间复杂度与空间复杂度

复杂度描述的是算法执行时间或者占用空间与数据规模的增长关系。

时间复杂度分析

代码执行时间随数据规模增长的变化趋势，叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。

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

T(n) = O(f(n))

其中T(n)表示算法执行的总时间，f(n)表示每行代码执行总次数，而n往往表示数据的规模。常量阶、低阶、系数对增长趋势不产生决定性影响，在做复杂度分析时可忽略这些项。

原则

1. 单段代码看高频：比如循环。
2. 多段代码取最大：比如一段代码中有单循环和多重循环，那么取多重循环的复杂度。
3. 嵌套代码求乘积：比如递归、多重循环等。
4. 多个规模求加法：比如方法有两个参数控制两个循环的次数，那么这是就取二者复杂度相加。

级别

多项式量级 随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长。

1. 常量阶 O(1)
2. 对数阶 O(logn)
3. 线性阶 O(n)
4. 线性对数阶 O(nlogn)
5. O(n²)平方阶、O(n³)立方阶……

非多项式量级 随着数据规模的增长，算法的执行时间和空间占用暴增，这类算法的性能极差

6. 指数阶 O(2ⁿ)
7. 阶乘阶 O(n!)

空间复杂度分析

空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。

类似于时间复杂度

其他复杂度

1. 最好情况时间复杂度（best case time complexity）

   在最理想的情况下，执行这段代码的时间复杂度

2. 最坏情况时间复杂度（worst case time complexity）

   在最糟糕的情况下，执行这段代码的时间复杂度

3. 平均情况时间复杂度（average case time complexity）

   加权平均时间复杂度/期望时间复杂度
   用代码在所有情况下执行的次数的加权平均值表示

4. 均摊时间复杂度（amortized time complexity）

   摊还分析、平摊分析。一种特殊的平均时间复杂度。
   在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果等于低级别复杂度。（重点1、高级别少数2、低高出现具有时序规律）