算法复杂度分析

终于放寒假了，松下一口气的博主可以专心地更新博客了，希望寒假能有更大的进步！
本系列在于记载我的算法学习笔录，强化学习，废话不多说，开始吧。

什么是复杂度分析？

1. 数据结构和算法解决的是“如何让计算机更快时间，更省空间的解决问题”。
2. 因此需要从执行时间和占用空间两个维度来评估数据结构和算法的性能。
3. 分别用时间复杂度和空间复杂度两个概念来描述性能问题，二者统称为复杂度。
4. 复杂度描述的是算法执行时间（或占用空间）与数据规模的增长关系。故称其为渐进时间（空间）复杂度

为什么要进行复杂度分析？

1. 和性能测试相比，复杂度分析有不依赖环境、成本低、效率高、易操作、指导性强的特点。
2. 掌握复杂度分析将能编写出性能更优秀的代码，有利于降低系统开发和维护成本

如何进行复杂度分析？

大O表示法

1. 来源

   算法的执行时间与代码的执行次数成正比，用 T(n) = O(f(n)) 表示，其中T(n)表示算法执行总时间，f(n)表示每行代码执行总次数，而n往往表示数据的规模。

2. 特点

   以时间复杂度为例，由于时间复杂度描述的是算法执行时间与数据规模的增长变化趋势，所以常量阶、低阶以及系数实际上对这种增长趋势不产生决定性影响。所以在做时间复杂度分析时忽略这些项。

复杂度分析法则

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

常用的复杂度级别

复杂度量级：

常用复杂度量级

• 多项式阶：随着数据规模的增大，算法的执行时间和空间占用，按照多项式的比例增长。包括：

  O(1) 、O(logn)、O(n) 、O(nlogn) 、O(n^2)... O(n^k).

• 非多项式阶：随着数据规模的增大，算法的执行时间和空间占用暴增（NP问题），这类算法性能极差。

  O(2^n) 、O(n!)

复杂度曲线

复杂度分析

首先我们要引入几个概念：最好情况时间复杂度（best case time complexity）、最坏情况时间时间按复杂度（worst case time complexity）、平均情况时间复杂度 (average case time complexity)、均摊时间复杂度(amortized time complexity)。

为什么要引入这4个概念？

1. 同一段代码在不同情况下时间复杂度会出现量级差异，为了更全面，更准确的描述代码的时间复杂度，所以引入这4个概念。
2. 代码复杂度在不同情况下出现量级差别时才需要区别这四种复杂度。大多数情况下，是不需要区别分析它们的。

例子：

// 全局变量，大小为 10 的数组 array，长度 len，下标 i。
int array[] = new int[10]; 
int len = 10;
int i = 0;

// 往数组中添加一个元素
void add(int element) {
   if (i >= len) { // 数组空间不够了
     // 重新申请一个 2 倍大小的数组空间
     int new_array[] = new int[len*2];
     // 把原来 array 数组中的数据依次 copy 到 new_array
     for (int j = 0; j < len; ++j) {
       new_array[j] = array[j];
     }
     // new_array 复制给 array，array 现在大小就是 2 倍 len 了
     array = new_array;
     len = 2 * len;
   }
   // 将 element 放到下标为 i 的位置，下标 i 加一
   array[i] = element;
   ++i;
}

该算法的最好情况时间复杂度(best case time complexity)为O(1);

最坏情况时间复杂度(worst case time complexity)为O(n);

均摊时间复杂度 (amortized time complexity) 为O(1)；

以上为本篇内容，若有不足之处，请诸位多多包涵，斧正。笔者在此谢过。