简介

数据结构和算法是为了解决代码性能以及节省资源的问题，所以就需要一个方法来考量代码执行效率是否超标，是否占用太多存储空间

这个方法就是 复杂度分析，学习数据结构和算法离不开 复杂度分析

算法的复杂度包括：时间复杂度和空间复杂度，两者以时间复杂度相对重要，因为在 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表示法分析？

有三种实用的方法：

1. 只关注循环次数最多的一段代码
2. 加法法则：总复杂度等于量级最大的那段代码复杂度
3. 乘法法则：嵌套代码复杂度等于嵌套内外代码复杂度的乘积
4. 多个数据规模相加

加法法则：总复杂度等于量级最大的那段代码复杂度

例子：

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)

常量的时间复杂度(按数量级递增)：

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) 最为常见，也是最难分析的一种复杂度。

一个简单的例子：

$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²)

相关工具

• VisuAlgo - 数据结构和算法动态可视化 (Chinese)
• 力扣 - LeetCode

Q.E.D.