杂度分析原来这么简单

川长思鸟来 2021-08-01 01:33 389阅读 0赞

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

作者 |  小鹿

来源 |  一个不甘平凡的码农

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 2]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 3]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 4]

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

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

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

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

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

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

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

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 5]

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

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

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

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 6]

**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个数字之和
    2int 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

1int 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

分析

\-------------------------------------------

在所有代码中，我们很容易寻找到存储空间相关的代码，就是第二行，申请了一个 n 大小的存储空间，所以空间复杂度为 O(n)。

**2、最常见的空间复杂度**

> O(1)、O(n)、O(n²)。

■ **O(1)**

> 常量级的时间复杂度表示方法，无论是一行代码，还是多行，只要是常量级的就用 O(1) 表示。

Example

1int i = 1;
    2int j = 2;
    3int sum = i + j;

分析

\-------------------------------------------

因为这三行代码，也就是常量级别的代码不随 n 数据规模的改变而改变。（循环、递归除外）

■ **O(logn) | O(nlogn)**

> 「**对数阶时间复杂度**」，最难分析的一种时间复杂度。

Example

分析

\-------------------------------------------

要求这段代码的时间复杂度就求这段代码执行了多少次，看下图具体分析。

![640?wx\_fmt=png][640_wx_fmt_png]

补充

\-------------------------------------------

不管是以 2 为底、以 3 为底，还是以 10 为底，可以把所有对数阶的时间复杂度都记为 O(logn)，因为对数之间可以转换的，参照高中课本。

■** O(m+n) | O(m\*n)**

> 参照上边讲到的加法和乘法法则。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 7]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 8]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 9]

**1、最好、最坏时间复杂度**

> 所谓的最好、最坏时间复杂度分别对应代码最好的情况和最坏的情况下的执行。

Example

分析：

\-------------------------------------------

1、最好情况就是数组的第一个就是我们要查找的数据，上边代码之执行一遍就可以，这种情况下的时间复杂度为最好时间复杂度，为 O(1)。

2、最坏的情况就是数组的最后一个才是我们要查找的数据，需要循环遍历 n 遍数组，也就对应最坏的时间复杂度为 O(n) 。

**2、平均时间复杂度**

> 平均时间复杂度需要借助概率论的知识去分析，也就是我们概率论中所说的加权平均值，也叫做期望值。

分析

\-------------------------------------------

比如上方的例子，假设我们查找的数据在数组中的概率为 1/2；出现在数组中的概率为 n/1,根据下边的公式就可以算出出现的概率为 1/2n 。

![640?wx\_fmt=png][640_wx_fmt_png 1]

然后我们再把每种情况考虑进去，就可以计算出平均时间复杂度。

![640?wx\_fmt=png][640_wx_fmt_png 2]

**3、均摊时间复杂度**

■什么是均摊时间复杂度？

> 比如我们每 n 次插入数据的时间复杂度为 O(1)，就会有一次插入数据的时间复杂度为 O(n)，我们将这一次的时间复杂度平均到 n 次插入数据上，时间复杂度还是 O(1)。

■ 摊还分析

■ 适用场景

> 一般应用于某一数据结构，连续操作时间复杂度比较低，但是个别情况时间复杂度特别高，我们将特别高的这一次进行均摊到较低的操作上。

■ 几种复杂度性能对比

![640?wx\_fmt=png][640_wx_fmt_png 3]

各个时间复杂度的性能

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 10]

本文作者：「小鹿」，运营个人订阅号「一个不甘平凡的码农」。

**推****荐****阅****读**

***1.***

***2. ***

***3.***

***4.***

![640?][640]

[640_wx_fmt_jpeg]: /images/20210731/d3b305d66bce45edb455276fb8430421.png?wx_fmt=jpeg
[640_wx_fmt_jpeg 1]: /images/20210731/cddba09c8ec743e68134baf7c9cc0aeb.png?wx_fmt=jpeg
[640_wx_fmt_jpeg 2]: /images/20210731/4315a66e0777415db19fa5a4e581899e.png?wx_fmt=jpeg
[640_wx_fmt_jpeg 3]: /images/20210731/4bf8702c83de420897eeaeb69b7b1342.png?wx_fmt=jpeg
[640_wx_fmt_jpeg 4]: /images/20210731/ee141769b8ae4d44bd5ba255f8611a26.png?wx_fmt=jpeg
[640_wx_fmt_jpeg 5]: /images/20210731/4911fd1e9d074752a900fabd0845e199.png?wx_fmt=jpeg
[640_wx_fmt_jpeg 6]: /images/20210731/11b3a20b7e664b678fb0d45d47a9dd4c.png?wx_fmt=jpeg
[640_wx_fmt_png]: /images/20210731/6873a09c00224a1f872870191aa21c95.png?wx_fmt=png
[640_wx_fmt_jpeg 7]: /images/20210731/67747dcad5b54ab298eba71b29713fd5.png?wx_fmt=jpeg
[640_wx_fmt_jpeg 8]: /images/20210731/98db21a62ebf4f31991c355865fdc1e3.png?wx_fmt=jpeg
[640_wx_fmt_jpeg 9]: /images/20210731/aa9f384c58a14901b7a739576cf12b5d.png?wx_fmt=jpeg
[640_wx_fmt_png 1]: /images/20210731/d7b580af2f4c428da3c19460a786c1e8.png?wx_fmt=png
[640_wx_fmt_png 2]: /images/20210731/35816fe4e2f84b8186888d5182a902d5.png?wx_fmt=png
[640_wx_fmt_png 3]: /images/20210731/cbb4913e98a74463b8314a1ba0c66ecd.png?wx_fmt=png
[640_wx_fmt_jpeg 10]: /images/20210731/a43735b706ed46d99815ef60cb4324de.png?wx_fmt=jpeg
[640]: /images/20210731/c46de32d9573484ba77033f7a73810ab.png?