【小猪佩奇漫画】| 复杂度分析原来那么简单！

矫情吗；* 2022-01-20 12:19 394阅读 0赞

##### 1、数据结构是用来干嘛的？ #####

> 数据结构与算法的诞生是让计算机「执行的更快」、「更省空间」的。

##### 2、用什么来评判数据结构与算法的好坏？ #####

> 从「执行时间」和「占用空间」两个方面来评判数据结构与算法的好坏。

##### 3、什么是复杂度？ #####

> 用「时间复杂度」和「空间复杂度」来描述性能问题，两者统称为复杂度。

##### 4、复杂度描述了什么？ #####

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

##### 1、和性能分析相比有什么优点？ #####

> 辅助度分析有不依赖执行环境、成本低、效率高、易操作、指导性强的特点。

##### 2、为什么要复杂度分析？ #####

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

##### 1、什么方法可以进行复杂度分析？ #####

> 方法：「大 O 表示法」

##### 2、什么是大 O 表示法？ #####

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

##### 3、大 O 表示法的特点？ #####

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

##### 4、复杂度分析法则 #####

*  \[单段代码看频率\]：看代码片段中「循环代码」的时间复杂度。
 *  \[多段代码看最大\]：如果多个 for 循环，看「嵌套循环最多」的那段代码的时间复杂度。
 *  \[嵌套代码求乘积\]：循环、递归代码，将内外嵌套代码求乘积去时间复杂度。
 *  \[多个规模求加法\]： 法有两个参数控制两个循环的次数，那么这时就取二者复杂度相加。

### 时间复杂度 ###

##### 1、什么是复杂度？ #####

> 所有代码的「执行时间 T(n)」 与每行代码的「执行次数n」 成正比【T(n) = O(f(n)) 】。

\#\#\#\#\#2、分析的三个方法 ■ 最多法则

> 忽略掉公式中的常量、低阶、系数，取最大循环次数就可以了，也就是循环次数最多的那行代码。

▍Example

1 // 求n个数字之和
    2 int xiaolu(int n) {
    3   int sum = 0;
    4   for (int i = 1; i <= n; ++i) {
    5     sum = sum + i;
    6   }
    7   return sum;
    8 }
    复制代码

--------------------

▍分析 第二行是一行代码，也就是常量级别，与 n 没有关系，可以忽略，四、五行代码是我们重点分析对象，与 n 有关，时间复杂度就是反映执行时间和 n 数据规模的关系。求 n 个数据之和需要执行 n 次。所以时间复杂度为 O(n)。

■ 加法法则

> 总复杂度等于循环次数最多的那段复杂度。

▍Example

1 int xiaolu(int n) {
     2   int sum = 0;
     3   //循环一
     4   for (int i = 1; i <= 100; j++) {
     5     sum = sum + i;
     6   }
     7   //循环二
     8   for (int j = 1; j <= n; j++) {
     9      sum = sum + i;
    10   }
    11 }
    复制代码

--------------------

▍分析 上边有两个循环，一个循环 100 次，另一个循环 n 次，我们选择循环次数最多的那一个且和「数据规模 n 」相关的循环。由上可知，我们很容易选出循环二，即和数据规模 n 有关，循环次数最多，循环次数最多的那段代码时间复杂度就代表总体的时间复杂度，为 O(n) ;

■ 乘法法则

> 当我们遇到嵌套的 for 循环的时候，怎么计算时间复杂度呢？那就是内外循环的乘积。

▍Example

1 for (int j = 1; j <= n; j++) {
    2     for(int i = 1; i <= n; i++)
    3     sum = sum + i;
    4 }
    复制代码

--------------------

▍分析 外循环一次，内就循环 n 次，那么外循环 n 次，内就循环 n\*n 次。所以时间复杂为 O(n²)。

### 空间复杂度 ###

##### 1、什么是空间复杂度？ #####

> 表示算法的「存储空间」与「数据规模」之间的增长关

▍Example