简介
数据结构和算法是为了解决代码性能以及节省资源的问题，所以就需要一个方法来考量代码执行效率是否超标，是否占用太多存储空间
这个方法就是 复杂度分析，学习数据结构和算法离不开 复杂度分析
算法的复杂度包括：时间复杂度和空间复杂度，两者以时间复杂度相对重要，因为在 Web 开发中，常见的性能优化策略都是以空间换时间，例如缓存系统
#为什么需要分析复杂度？ 分析代码的复杂度可以知道，代码执行效率、消耗资源，以便优化，写出更高质量的代码。
掌握了复杂度分析，在编写代码的，会不经意的估算自己写的代码是否“合格”，有一种一眼扫过，尽在掌握之中的感觉，并且不需要额外取付出时间，那么不划算吗？
大 O 表示法
先来看一段代码：
$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表示法分析？
有三种实用的方法：
- 只关注循环次数最多的一段代码
- 加法法则：总复杂度等于量级最大的那段代码复杂度
- 乘法法则：嵌套代码复杂度等于嵌套内外代码复杂度的乘积
- 多个数据规模相加
加法法则：总复杂度等于量级最大的那段代码复杂度
例子：
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²)，所以这三段代码中，量级最大的是第三个循环，所以作为函数的时间复杂度
乘法法则：嵌套代码复杂度等于嵌套内外代码复杂度的乘积
具体代码：
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²)
多个数据规模相加
例如，一个代码段中有两个循环，循环的次数由两个参数决定，这就是两个数据规模，那么我们无法得知它们谁的量级大，所以需要将它们相加之后作为代码段的复杂度
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)
常量的时间复杂度(按数量级递增)：
- 常量阶
O(1) - 对数阶
O(logn) - 线性阶
O(n) - 线性对数阶
O(nlogn) - 平方阶
O(n²)、立方阶O(n³)... K次方阶O(n^k) - 指数阶
O(2^n) - 阶乘阶
O(n!)
O(1)
代码段中不包含循环语句、递归，那么时间复杂度都是 O(1)
O(logn)、O(nlogn) 最为常见，也是最难分析的一种复杂度。
一个简单的例子：
$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)。
#空间复杂度分析 表示算法的存储空间与数据规模之间的增长关系，全称：渐进空间复杂度
function call() {
$var = 1;
$arr = [$n];
}
代码第二行申请了一个大小为 1 的空间存储变 var，因为是常量所以忽略。
第三行申请了一个大小为 n 的空间存储变量，所以整个代码段空间复杂度为：O(n)
常量的空间复杂度:
O(1)O(n)O(n²)
