# 简介 数据结构和算法是为了解决代码性能以及节省资源的问题，所以就需要一个方法来考量代码执行效率是否超标，是否占用太多存储空间 这个方法就是 **复杂度分析**，学习数据结构和算法离不开 **复杂度分析** 算法的复杂度包括：**时间复杂度和空间复杂度**，两者以时间复杂度相对重要，因为在 Web 开发中，常见的性能优化策略都是以空间换时间，例如缓存系统 #为什么需要分析复杂度？ 分析代码的复杂度可以知道，代码执行效率、消耗资源，以便优化，写出更高质量的代码。 掌握了复杂度分析，在编写代码的，会不经意的估算自己写的代码是否“合格”，有一种一眼扫过，尽在掌握之中的感觉，并且不需要额外取付出时间，那么不划算吗？ # 大 O 表示法 先来看一段代码： ```php $sum = 0; for ($i=0; $i < n; ++$i) { $sum =+ $i; } ``` 在不同的环境下执行，结果是不同的，所以我们假设每行代码执行时间为：time 那么 **2、3** 行代码都需要执行一次，就是 `2*time`，**4、5** 行代码循环次数分别是 `n`，那么就是 `2n*time`，这段代码的执行时间就是：`T(n) = (2+2n)\*time`，从这里可以看出来，**所有代码执行时间T(n) 与 每行代码执行次数 n 是成正比** 大O表示法公式： `T(n)=O(f(n))` - `T(n)`：所有代码执行时间 - `f(n)`：每行代码执行次数的总和 - `O`：表示 `T(n)` 与 `f(n)` 成正比 - `n`：表示数据规模 所以上面的代码使用大 O 表示法来分析就是：`T(n) = O(2+2n)`，它不表示具体执行时间，而是表示 **代码执行时间随着数据规模增大的变化趋势**，也叫 **渐进时间复杂度**，简称 **时间复杂度** 既然它是表示一种变化趋势，那么可以将公式中的低阶、系数、常量这三部分定量值忽略，因为它随着时间变化不会产生任何影响，只需要记录一个最大量级即可，那么上面那段代码的复杂度可以这样写：`T(n) = O(n)` # 如何使用大O表示法分析？ **有三种实用的方法：** 1. 只关注循环次数最多的一段代码 2. 加法法则：总复杂度等于量级最大的那段代码复杂度 3. 乘法法则：嵌套代码复杂度等于嵌套内外代码复杂度的乘积 4. 多个数据规模相加 ## 加法法则：总复杂度等于量级最大的那段代码复杂度 例子： ```php function count(){ # exmple 1 $sum1 = 0; for ($i=0; $i <= 100; ++$i) { $sum1 =+ $i; } # exmple 2 $sum2 = 0; for ($i=0; $i < n; ++$i) { $sum2 =+ $i; } # exmple 3 $sum3 = 0; for ($i=0; $i < n; $i++) { $sum3 += $i; for ($j=0; $j < n; $j++) { $sum3 += $j; } } return $sum1 + $sum2 + $sum3; } ``` 上面三个循环分别求 $sum1、$sum2、$sum3 的值 第一个循环的次数为常量，所以忽略不分析，第二个循环和第三个循环分别是：O(n)、O(n²)，所以这三段代码中，量级最大的是第三个循环，所以作为函数的时间复杂度 ## 乘法法则：嵌套代码复杂度等于嵌套内外代码复杂度的乘积 具体代码： ```php function call() { for ($i=0; $i < $n; $i++) { $ret =+ f($i); } function f($n) { for ($i=0; $i < $n; $i++) { $sum =+ $i; } return $sum; } } ``` 上面代码中，循环中嵌套循环，第 3 行代码执行的次数是 `n`，但是它同时调用了 `f` 函数，算上函数内的执行次数 `n`，所以时间复杂度是：`T(n) = T1(n) * T2(n) = O(n*n) = O(n²)` ## 多个数据规模相加 例如，一个代码段中有两个循环，循环的次数由两个参数决定，这就是两个数据规模，那么我们无法得知它们谁的量级大，所以需要将它们相加之后作为代码段的复杂度 ```php function call($m,$n) for ($i=0; $i < $m; ++$i) { $sum_1 = $sum_1 + $i; } for ($i=0; $j < $n; ++$j) { $sum_2 = $sum_2 + $j; } return $sum_1 + $sum_2; } ``` 无法得知 `m`、`n` 谁的量级大，所以记为：`O(m+n)` ## 常量的时间复杂度(按数量级递增)：  1. 常量阶 `O(1)` 2. 对数阶 `O(logn)` 3. 线性阶 `O(n)` 4. 线性对数阶 `O(nlogn)` 5. 平方阶 `O(n²)`、立方阶 `O(n³)` ... K次方阶 `O(n^k)` 6. 指数阶 `O(2^n)` 7. 阶乘阶 `O(n!)` **O(1)** 代码段中不包含循环语句、递归，那么时间复杂度都是 O(1) **O(logn)、O(nlogn)** 最为常见，也是最难分析的一种复杂度。 一个简单的例子： ```php $i = 1; while($i <= n){ $i *= 2; } ``` 每次循环都乘于 2，当大于 `n` 时就停止循环，这样的增长趋势，变量 `i` 的取值是一个等比数列，所以这段代码的时间复杂度是：`O(log₂n)`  上面的的对数底是 2，但是不管底是多少，时间复杂度都记为：`O(logn)` > 对数之间是可以互相转换的，log₃n = log₃2 \* log₂n > 所以：O(log₃n) = O(C * log₂n) > C=log₃2 是一个常量，忽略之后就成了：O(Cf(n)) = O(f(n)) > 所以不管底是多少都统一记为：`O(logn)` 如果一段代码的时间复杂度是 `O(logn)`，我们循环执行 `n` 遍，时间复杂度就是 `O(nlogn)` 了，比如，归并排序、快速排序的时间复杂度都是 `O(nlogn)`。 #空间复杂度分析 表示算法的存储空间与数据规模之间的增长关系，全称：**渐进空间复杂度** ```php function call() { $var = 1; $arr = [$n]; } ``` 代码第二行申请了一个大小为 1 的空间存储变 `var`，因为是常量所以忽略。 第三行申请了一个大小为 `n` 的空间存储变量，所以整个代码段空间复杂度为：`O(n)` **常量的空间复杂度:** - `O(1)` - `O(n)` - `O(n²)` # 相关工具 - [VisuAlgo - 数据结构和算法动态可视化 (Chinese)](https://visualgo.net/zh) - [力扣 - LeetCode](https://leetcode-cn.com/)