[数据结构与算法]算法复杂度分析(3600字)

前言

复杂度分析是算法学习的基础，也是算法的精髓。针对每一个数据结构和算法，通过复杂度分析，我们能够更加科学地判断其质量好坏。因此，复杂度分析非常重要。

一、复杂度分析的意义

虽然，我们通过把代码运行一遍，能够很快得出运行时间，内存占用的数据。然而，在实际的生产测试环境中，由于硬件的不同，这种方法不够准确。

另外，当我们使用不同的测试数据，也会对测试结果产生较大影响。比如排序，众所周知，在数据量小的时候插入排序会比快排快很多。在极端情况下，比如数据已经排好序时，有些排序算法甚至不会做任何操作！

而复杂度分析其实就是一种帮助你在不运行代码的情况下，估算代码执行时间和效率的方法。

二、复杂度分析基础

1. 大$O$复杂度表示法

代码（示例）：

int cal(int n) {
	int sum = 0;
	int i = 1;
	for (; i <= n; i++) {
		sum = sum + i;
	}
	return sum;
}

对芯片来说，代码的每一条语句都执行了类似于：读数据—>运算—>写数据这样的操作。

我们假设每条语句在同一台电脑上的运行时间一样，设为 $unit\_time$。

我们很轻易就能看出来执行第2、3、7行分别需要1个 $unit\_time$，而第4、5行代码循环运行了n遍，需要
$(2n+3)\times$$unit\_time$的执行时间。

综上可得，这段很silly的示例代码总的执行时间是
$(2n+3)\times$$unit\_time$。通过这个例子，得出一个简单结论，任何一段代码的总的执行时间，记为 $T(n)$（该例子中的 $(2n+3)\times$$unit\_time$）与每一条语句的执行次数的累加数（该例子里的$2n+3$）成正比。

我们可以把这一规律总结为如下公式：
$$T(n)=O(f(n))$$其中$T(n)$表示代码执行的总时间，$n$表示数据规模，$f(n)$表示每条语句执行次数的累加和。

套用这个例子中的
$$T(n)=(2n+3)\times unit\_time=O(2n+3)$$但是，我们并不使用大$O$表示代码的真正执行时间，而用它来表示代码执行时间随着数据规模增大的变化趋势。

当$n$很大的时候，$f(n)$多项式中的低阶项、常量、系数并不决定增长的趋势，我们忽略这些部分，只保留最大量级，也就是最高阶。

所以，上面例子中的 $O(2n+3)$ 应该记为 $O(n)$。

2. 时间复杂度分析方法

时间复杂度全称为渐进时间复杂度，表示代码执行时间随着数据规模增大的变化趋势。

2.1 加法法则

代码总的复杂度等于量级最大的那段代码的复杂度

代码（示例）：

int cal(int n) {
	int sumOne = 0;
	int k = 1;
 	for (; p <= 100; ++p) {
 		sumOne = sumOne + p;
	}

 	int sumTwo = 0;
 	int i = 1;
 	int j = 1;
 	for (; i <= n; ++i) {
		j = 1;
 		for (; j <= n; ++j) {
 			sumTwo = sumTwo + i * j;
 		}
	}

 	return sumOne + sumTwo;
}

求这段代码复杂度的方法是分别求2-6行，8-19行的代码复杂度，然后求和。

2-6行需要的执行时间是$100\times unit\_time$，可以表示为 $O(1)$。

8-19行需要的执行时间是$(2n^2+2n+4)\times unit\_time$，可以表示为 $O(n^2)$。

而总的时间复杂度，我们取量级最大的那部分代码的时间复杂度。这条法则就是加法公式：

$if$
$$T1(n)=O(f(n));T2(n)=O(g(n))$$

$then$
$$T(n)=T1(n)+T2(n)=max(O(f(n)),O(g(n)))$$
$$T(n)=O(max(f(n),g(n)))$$

2.2 乘法法则

嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

代码（示例）：

int cal(int n) {
	int ret = 0;
	int i = 1;
 	for (; i <= n; i++) {
 		ret = ret + f(i);
	}
}

int fun(int n) {
	int sum = 0;
 	int i = 1;
	for (; i <= n; i++) {
 		sum = sum + i;
 	}
 	return sum;
}

根据前面所述的方法我们很容易估算出上述代码中 cal( ) 函数z中4-6行的时间复杂度是 $O(n)$，fun( ) 函数的时间复杂度也是 $O(n)$。

而我们的乘法法则规定：
$if$
$$T1(n)=O(f(n));T2(n)=O(g(n))$$
$then$
$$T(n)=T1(n)\times T2(n)=O(f(n))\times O(g(n))$$
$$T(n)=O(f(n)\times g(n))$$

所以，在这个例子中套用乘法公式cal()函数的时间复杂度$$T(n)=T1(n)\times T2(n)=O(n\times n)=O(n^2)$$

3. 空间复杂度

空间复杂度仍然使用 大 $O$ 复杂度表示法。空间复杂度的全称是渐进空间复杂度，表示算法的存储空间与数据规模的增长关系。

public void reverse(int a[], int n) {
	int tmp[] = new int[n];
	for (int i = 0; i < n; ++i) {
		tmp[i] = a[n-i-1];
	}
 	for (int i = 0; i < n; ++i) {
 		a[i] = tmp[i];
	}
}

在第3行，申请了一段空间来存储变量 i ，但是这是一个常量阶的，与数据规模n无关，在表示空间复杂度时可以将之省略。而第二行代码中申请的给数组的存储空间的大小是 n ，剩下的代码没有占用更多的空间。所以整段代码的空间复杂度是 $O(n)$。

可以与时间复杂度进行类比，常见的类型与之相同，比时间复杂度简单。

总结

虽然代码千差万别，但是常见的时间复杂度并不多。总结一下只有以下这几种：

1. $O(1)$

只要代码的执行时间不随规模$n$变化，就是常量级时间复杂度，全部记作 $O(1)$。

代码（示例）：

int cal(int n) {
	int sumOne = 0;
	int k = 1;
 	for (; p <= 100; ++p) {
 		sumOne = sumOne + p;
	}
}

该段代码复杂度即为 $O(1)$。

2. $O(logn)、O(nlogn)$

对数阶时间复杂度比较常见，但最难分析。下面用一个简单的具体例子作介绍：

代码（示例）：

int i = 1;
while (i <= n) {
 	i = i * 2;
}

这段代码里的 i 实际上是一个等比数列，i 的取值序列是
$2^0,2^1,2^2,...,2^x$。当 i ($2^x$) > n 时，该循环就会终止。求出 x 的值就是 ${\log }_{2}n$ ，因此这段代码的时间复杂度就是$O(lo{g}_{2}n)$。

但是对数的“底”即 ${\log }_{2}n$ 中的2对代码执行时间增加趋势的影响很小，微乎其微，所以我们对于任意复杂度为 $O(lo{g}_{a}n)$ 的算法，都把时间复杂度实际记作 $O(logn)$。

3. $O(m+n)、O(mn)$

有一种比较特别的情况，代码的时间复杂度由数据规模决定，下面看个例子。

代码（示例）：

int cal(int m, int n) [
	int sumOne = 0;
	int i = 1;
 	for (; i <= m; ++i) {
		sumOne = sumOne + i;
	}
 	int sumTwo = 0;
	int j = 1;
 	for (; j <= n; ++j) {
		sumTwo = sumTwo + j;
	}
	return sumOne + sumTwo;
}

该例子中的代码里，m 和 n 表示两个无关的数据规模。关于这两个数据规模，因为在事先无法估出谁的量级更大，所以在表示时间复杂度的时候，我们不能省略其中任何一个。综上，上面代码的时间复杂度为 $O(m+n)$。