算法复杂度分析入门

执行效率资源消耗是评价一个算法优劣最核心的两个点,分别代表运行这个算法所需要消耗的时间空间

分析运行一个算法需要消耗多少时间的行为叫做时间复杂度分析,同理,分析运行一个算法需要消耗多少空间的行为叫做空间复杂度分析

实际上,如果我们直接将算法运行一遍,记录下运行过程中消耗的时间和空间,就可以得到这个算法准确的资源消耗情况。这种思路确实是可以,我们可以管这种方法叫做事后统计法

但是这样得出来的结果变量太多,比如测试环境的硬件性能,软件(操作系统 / SDK 等)版本,测试的数据规模,甚至是实现算法所用的编程语言,都对结果都有或多或少的影响。而如果想要测试条件覆盖尽可能多的情况,就会产生极其巨大的工作量,即便是一个很简单的算法,都需要非常大量的测试。这显然不是一个可取的方法。

因此,事后统计法一般只适合在特定环境下给特定的程序做性能测试(例如很多程序在上线之前都要做压力测试),不适合用来对一个通用型的算法或程序做无差别的性能评估。

大 O 表示法

为了在程序运行前,不依赖具体测试结果,就能无差别的评估一个算法的执行效率,工程师们使用了一个数学中的概念:大 O 符号,又称渐进符号

大 O 表示法是目前做算法复杂度分析时所使用的行业标准,这是一个抽象的概念,它表示的不是某个具体的值,而是一种趋势

比如下面是一个计算 1 + 2 + 3 + ... + n 的累加式的函数:

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

假定计算机每执行一行代码所消耗的时间为 t,那么在这个例子中,第二行是一个简单的赋值操作,消耗时间为 t,第四、五行是一个循环操作,消耗时间为 2n*t,那么程序总消耗时间为 T(n)= t + 2nt

再看下面这个例子:

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

在这个例子中,第二行耗费的时间为 t,三、四、五行是一个双层循环,其中第四、五行耗费的时间是 2n^2*t,第三行耗费的时间是 n*t,那么总的时间消耗为 T(n)=t+nt+2n^2t

通过两个例子,可以发现一个明显的规律:代码的总执行时间 T(n) 与每行代码的执行次数 n 成正比。

利用大 O 符号,我们可以把这个规律表示为:T(n) = O(f(n))

这个表达式称之为 大 O 表达式,其中:T(n) 表示程序总的执行时间,f(n) 表示每行代码执行的总次数,n 表示数据规模的大小,O 表示 T(n) 与 f(n) 成正比。

所以,大 O 表达式实际上并不是代表程序具体执行的时间,而是表示代码执行时间随数据规模增长的变化趋势,因此,也叫做渐进时间复杂度(asymptotic time complexity),简称时间复杂度

在大 O 表达式中,当 n 趋近于无限大时,公式中的常量、系数、低阶部分对增长趋势的影响非常小,可以忽略不计,因为现代计算机的执行速度非常快,通常能达到每秒几百亿次,因此我们只需要记录一个最大量级即可。

因此,第一个例子中我们得出的 T(n)=t+2nt,忽略常量 t 和系数 2t 之后,用大 O 表示法为:T(n)=O(n)

第二个例子中的 T(n)=t+nt+2n^2t 忽略常量和系数,保留最大量级后,用大 O 表示法为:T(n)=O(n^2) (这个例子在后文“加法法则”中会有更详细的解释)

这种分析思路来源于数学中的 渐进分析 方法,计算机科学实际上就是从数学中独立出来的一个分支,在解决比较底层和抽象层面的问题上,用的基本都是数学方法。

时间复杂度分析

时间,是世间最宝贵的资源。

在算法的复杂度分析中,时间复杂度分析通常比空间复杂度分析更重要,也更复杂。因为计算机的空间(硬件)是可以扩容的,而人类目前的科技能力,还远远达不到“扩容时间”的水平。

因此,我们先重点关注时间复杂度分析。

分析技巧

分析代码的时间复杂度一般都需要按照具体逻辑具体分析,不过也有一些可以帮助我们简化分析的技巧,下面分享两个最常用的分析技巧。

乘法法则

如下示例:

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

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

这其实是一个拆成两个函数的嵌套循环,如果函数 foo() 的循环体中是一个简单的操作,那么两个函数的时间复杂度都是 O(n),但是函数 foo() 的循环体中调用了函数 bar(),而函bar()的时间复杂度是O(n),因此函数 foo() 的时间复杂度就是 O(n)*O(n) = O(n^2)

如上所示,复杂度分析的乘法法则抽象为数学公式就是:

\begin{equation} \begin{split} T(n) &=T_1(n) * T_2(n) \\ &= O(f(n)) * O(g(n)) \\ & = O(f(n)*g(n)) \end{split} \end{equation}

当碰到嵌套循环代码时,可以使用乘法法则帮助我们分析复杂度:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。

例如外层循环时间复杂度为 O(f(n)),内层循环时间复杂度为 O(g(n)),那么总的时间复杂度就是 O(f(n)*g(n))

加法法则

如下示例:

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

	sum = sum + foo(n);

	sum = sum + bar(n);

	return sum;
}

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

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

根据上面的计算规则,我们知道函数 foo() 的时间复杂度 T_1(n) = O(n),函数 bar() 的时间复杂度 T_2(n) = O(n^2),而函数 cal() 中的第一段是个 100 次的循环,虽然是个循环,但是个已知次数的常量循环,与数据规模 n 无关。

同时,随着数据规模的增大,O(n^2) 的时间复杂度会远高于 O(n),此时只需要取复杂度最高的值即可,因此总复杂度

\begin{equation} \begin{split} T(n) &= T_1(n) + T_2(n) \\ &= O(n) + O(n^2) \\ &= max(O(n),O(n^2)) \\ &= O(n^2) \end{split} \end{equation}

如上所示,复杂度分析的加法法则抽象为数据公式就是:

\begin{equation} \begin{split} T(n) &= T_1(n) + T_2(n) \\ &= O(f(n)) + O(g(n)) \\ &= max(O(f(n)),O(g(n))) \\ &= O(max(f(n),g(n))) \end{split} \end{equation}

当碰到程序中包含多个子函数/算法时,可以使用加法法则帮助我们分析复杂度:总复杂度等于量级最大的那段代码的复杂度。

如果在多段代码中,无法确定哪一段复杂度最大,那么直接相加即可。

T_1=O(n)T_2=O(m),在无法确定 m 和 n 谁更大时,则 T(n)=O(n+m)

大部分情况下,复杂的算法或者程序都是由简单的算法步骤组合而成,这两个技巧有助于我们在分析复杂算法的时候理清思路,不被绕晕。理解这两个法则之后会发现,都是很自然的规律,所以不用刻意去记忆和套用,多分析几个实例,自然就熟悉了,而且可以总结出更适合自己思维习惯的技巧。

分析实例

虽然代码千变万化,但是得益于数学思想的高度抽象性,以下几种形式就能囊括绝大部分算法的复杂度(按时间复杂度量级升序排列):

  1. 常数阶:O(1)

  2. 对数阶:O(log\ n)

  3. 线性阶:O(n)

  4. 线性对数阶:O(n*log\ n)

  5. k次方阶:O(n^k)

  6. 指数阶:O(k^n)

  7. 阶乘阶:O(n!)

以上 7 种量级的复杂度,可以分为两类:多项式量级非多项式量级,其中非多项式量级只有两个:O(k^n) 和 O(n!)

时间复杂度为非多项式量级的算法问题也叫做 NP(Non-Deterministic Polynomial 非确定多项式)问题

随着数据规模的增大,非多项式时间复杂度量级的算法,执行时间会急剧增加,所以,非多项式时间复杂度的算法一般效率都很低,除非是确定性的小规模数据应用场景,大多是情况下都不应该使用,否则容易造成程序性能急剧下降。

我们主要看下几种常见的多项式时间复杂度的例子:

常数阶

首先还是要重申一下大 O 表达式的概念:表示程序执行时间随数据规模增长的变化趋势。

所以 O(1) 并不是说只执行一行代码,而是指执行时间不会随着数据规模的增大而无增大,比如下面这个例子:

int sum() {
	int i = 1;
	int j = 2;
	return i + j;
}

即便需要执行 3 行代码,它的时间复杂度也是 O(1),而不是 O(3)

通常情况下,如果一段代码里没有循环、递归,其时间复杂度都是 O(1),其函数图形如下

线性阶

线性阶也是一种非常常见的时间复杂度量级,比如文章一开始我们就分析过的第一个例子:

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

这就是一个典型的 O(n) 复杂度的例子,程序执行时间的增长幅度和数据规模的增长幅度保持一致。

通常情况下,一个简单的单层循环的时间复杂度就是 O(n) ,其函数图形如下:

对数阶

对数阶是也是很常见,但是分析起来复杂一些的时间复杂度类型。看下面这个例子:

int foo(int n) {
	int i = 1;
	while (i < n) {
		i = i * 2;
	}
	return i;
}
// 这段代码的逻辑是: i 在循环中不断乘 2 ,直到 i >= n 时,退出循环

根据上文的分析,我们只要分析出这个循环执行了多少次,就能算出这段代码的时间复杂度。

实际上就是等比数列:

1*2*2*2*2\cdots = n

也就是 2^x = n 求解 x,高中数学给了我们答案:x = log_2n ,所以这个循环执行了 log_2n 遍,因此这段代码的时间复杂度为 O(log_2n)

如果我们把上述例子中的常量乘数 2 换成 3,那么时间复杂度就变成了 O(log_3n)

根据对数的 链式运算,我们知道 log3n = log32 x log2n,那么 O(log3n) = O(log32 x log2n),其中 log32 是一个常量系数,基于上文我们的分析,在大 O 表示法中,可以忽略系数,即:

O(C*f(n)) = O(f(n))

也就是说,在 O(log_kn) 这样的对数阶复杂度中,无论底数常量 k 是多少,复杂度都是一样的,所以我们统一忽略底数,将对数阶复杂度表示为:

O(log\ n)

其函数图像图下:

线性对数阶

理解了对数阶 O(logn) 之后,理解线性对数阶就容易很多了。将一个 O(logn) 复杂度的步骤,执行 n 遍,其复杂度就是 O(nlogn)

如下是一个简单的 O(nlogn) 时间复杂度程序的示例:

int foo(int n) {
	for(int j = 1; j <= n; j++) {
		int i = 1;
		while (i <= n) {
			i = i * 2;
		}
	}
}
// 这段代码中,外面套的这层 for 循环并没有什么实际意义,仅作为演示说明

根据前文我们提到的乘法法则,这段代码的时间复杂度很容易计算得出:

T(n) = O(n) * O(log_n) = O(nlog_n)

这就是线性对数阶,其函数图像如下:

K 次方阶

这也是最常见的时间复杂度之一,K 是常数,如下是一个非常简单的平方阶时间复杂度示例:

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

利用上文介绍的乘法法则,很快就能计算出这段代码的时间复杂度:

T(n)=O(n)*O(n)=O(n^2)

其函数图像图下:

⚠️ 注意:次方阶 O(n^k) 容易和指数阶 O(k^n) 混淆,它们都是指数函数,区别在于数据规模 n 是底数还是指数,如果数据规模 n 是指数的话,复杂度会急剧上升,参考前文的 NP 问题

分析进阶

以上都是一些逻辑相对简单的例子,我们在实际编写程序的时候,通常会有一些提升效率的操作和技巧,这会让我们在分析时间复杂的过程中要考虑的因素更多一些。

如下示例:

// array 是一个数组
int find(int[] array, int x) {
	for (int i = 0; i < array.length -1 ; i++) {
		if (array[i] == x) {
			return i;
		}
	}
	return -1;
}
// 这个函数的逻辑是找出数组 array 中目标数值 x 的下标位置,如果数组中没有目标值 x ,就返回 -1

这段程序是在遍历数组,但又不完全是在遍历数组。因为循环中间的这个 return 导致我们不得不思考一个问题:如果 x 就在数组的第一位,那么这个函数就并不会遍历整个数组,而是在第一次循环就退出,这个时候时间复杂度就是 O(1),但是如果 x 在数组中的最后一位,或是数组中根本不存在 x,那么就需要遍历整个数组,这个时候时间复杂度就变成了 O(n) (n 是数组的长度)

所以这段代码在不同情况下,时间复杂度是不一样的。

为了表示不同情况下的时间复杂度,我们需要再引入三个概念:最好时间复杂度最坏时间复杂度平均时间复杂度

最好/最坏时间复杂度

最好和最坏时间复杂度比较简单,顾名思义,它们分别表示在最理想和最不理想的情况下代码的时间复杂度

对应上述的例子,就是 x 在数组第一位,和 x 在数组最后一位或者不在数组中的情况。

平均时间复杂度

很明显,最理想和最不理想的情况发生的概率都很低,这样评估复杂度的话,不够准确。为了更准确的评估这种情况下的时间复杂度,我们就需要另一个概念:平均时间复杂度。

还是上面那个例子x 在数组中位置的可能性有 n+1 种情况,分别是在数组中的任意位置和不在数组中。我们把每种情况下需要执行的次数加起来,再除以 n+1 就可以得到平均情况下的时间复杂度:

\frac{1+2+3+\cdots+n+n}{n+1}

我们把这个式子稍微简化一下,我们知道

1+2+3+\cdots+n=\frac{n(n+1)}{2}

推导过程可以看 这里

所以:

\frac{1+2+\cdots n+n}{n+1}=\frac{n(n+1)/2+n}{n+1}=\frac{n(n+3)}{2(n+1)}

忽略常量和系数之后可以看出,这是个线性阶的时间复杂度(看不出来的话带入几个数算算也行),也就是 O(n),这个就是平均时间复杂度。

但是这样计算平均时间复杂度,还是不够准确,因为每种情况出现的概率并不一样。首先从大方向上看, X 只能是在或不在数组中,这两种情况准确的概率统计起来并不容易。为了方便理解,我们将其概率分别假设为 1/2 ,同时x 在数组中不同位置出现的概率也分别为 1/n,所以,根据概率乘法法则x 出现在数组中各个不同位置的概率为:

\frac{1}{2}\star\frac{1}{n}=\frac{1}{2n}

然后,我们再将各种情况的概率因素考虑进去,平均时间复杂度的计算就变成了:

1*\frac{1}{2n}+2*\frac{1}{2n}+\cdots+n*\frac{1}{2n}+n*\frac{1}{2}=\frac{3n+1}{4}

这个值就是概率论中的加权平均值,也叫做期望值,所以更准确的平均时间复杂度,应该叫做加权平均时间复杂度,或者期望时间复杂度

\frac{3n+1}{4}

去掉常量和系数之后,用大O表达式描述,加上概率之后的平均复杂度还是 O(n),有时简单平均和加权平均复杂度是一样的,也有时会不一样。

平均时间复杂度的计算方式确实有些复杂,但是平时使用得其实并不多,多数情况下使用单一复杂度评估即可。

均摊时间复杂度

上文提到,只有在一些特殊情况下才需要使用平均时间复杂度去评估程序,而均摊时间复杂度更加特殊,使用到的情况更少。如下代码:

// array表示一个长度为n的数组 
// 代码中的array.length就等于n 
int[] array = new int[n]; 
int count = 0; 
void insert(int val) { 
	if (count == array.length) {
		int sum = 0; 
		for (int i = 0; i < array.length; ++i) { 
			sum = sum + array[i]; 
		} 
		array[0] = sum; 
		count = 1; 
	} 
	array[count] = val; 
	++count; 
}

这段代码实现了一个往数组中插入数据的功能。当数组满了之后,也就是代码中的 count == array.length 时,我们用 for 循环遍历数组求和,并清空数组,将求和之后的 sum 值放到数组的第一个位置,然后再将新的数据插入。但如果数组一开始就有空闲空间,则直接将数据插入数组。

我们分析下这段代码的最好、最坏和平均时间复杂度。

最好的情况就是数组刚好有空闲,于是直接插入即可,时间复杂度是 O(1),最坏的情况就是刚好 count == array.length ,这个时候需要遍历整个数组,时间复杂度是 O(n)

然后我们再来分析一下期望时间复杂度,这里一共有 n+1 种情况,其中有空位的种情况有 n 种的,没有空位的情况有一种,而且每种情况出现的概率都是 n+1,因此,期望时间复杂度为:

1*\frac{1}{n+1}+1*\frac{1}{n+1}+\cdots+1*\frac{1}{n+1}+n*\frac{1}{n+1}=\frac{2n}{n+1}

省略系数和常量之后,就是 O(1)

但是这个例子中分析平均时间复杂度,其实并不需要这么复杂的计算,为什呢?

我们对比一下这两个例子,会发现两个很大的区别:

1. find() 函数中,只有在极少数最理想的情况下,时间复杂度才会是 O(1),而大部分情况下时间复杂度都是 O(n),但是 insert() 函数很不一样,在大部分情况下,时间复杂度都是 O(1),只有在极少数的最不理想情况下,时间复杂度才会是 O(n)

2. insert() 函数中 O(n) 操作和 O(1) 操作有很强的规律性和顺序性:每一次 O(n) 的插入操作之后,紧接着 n-1 次的 O(1) 插入操作,如此循环

针对这种更加特殊的情况,我们还有一种更加方法的分析方法:摊还分析法,通过这种方法分析得出的时间复杂度我们称之为:摊还时间复杂度

这种分析方法的核心思路是 分组

我们看这个例子,每一次 O(n) 复杂度的插入操作之后,紧接着 n-1 次 O(1) 复杂度的插入操作,那么我们把这 n 次操作分成一组,将第一次 O(n) 耗时多的操作中消耗的时间,均摊到后面 n-1 耗时少的操作中,这样一组连续操作下来均摊的时间复杂度就是 O(1)。这就是摊还分析方法的大致思路。

总结一下就是,在一个程序中,大部分时候时间复杂度都很低,只有极少数时候时间复杂度比较高,而且这些操作之间存在很强的顺序关系,这个时候就可以把这个程序的操作进行分组,将耗时多的情况下多消耗的时间,均摊到耗时少的情况中去,这样就能更快的得到这个程序的时间复杂度。

从这个例子中,我们也能看出来,在能够使用摊还分析方法的场景中,一般均摊时间复杂度就等于最好时间复杂度

通过上述平均时间复杂度和均摊时间复杂度的两个例子,我们能看出来,平均时间复杂度是分析程序时间复杂度的一种特殊情况,而均摊时间复杂度又是平均时间复杂度的一种特殊情况,因此,会用到均摊时间复杂度的场合就更少了。所以,我们重点是要知道这种分析思路,并不用花太多精力在去区分和记忆。

上文花了很长的篇幅讲了时间复杂度分析,理解了这些内容,下面我们再来分析空间复杂度,就简单很多了。

空间复杂度分析

分析空间复杂度和分析时间复杂度的框架是一致的,都是使用大 O 表达式,也都是表示数据规模与复杂度之间的趋势关系。那么,类比一下,空间复杂度全称就是渐进空间复杂度(asymptotic space complexity),表示算法消耗的存储空间与数据规模之间的增长关系

空间复杂度分析相较于时间复杂度分析,要简单很多。看下面这个例子:

void print(int n) {
	int[] array = new int[n];
	for(int i = 0; i <= n-1; i++) {
		array[i] = (int)(Math.random()*100);
	}
	for(int j = 0; j <= n-1; j++) {
		System.out.println(array[j]);
	}
}

这段代码是将一个长度为 n 的数组用 100 以内的随机数填满,然后再遍历输出。

在空间使用方面,除了第二行申请了一个长度为 n 的数组 array,其他操作均没有涉及,因此这段代码的空间复杂度和 n 的大小成正比,也就是 O(n)

常用的空间复杂度比常用的时间复杂度也少很多,一般就是 O(1)、 O(n)、 O(n^2) 这三种。如果碰到特殊情况,使用分析时间复杂度的思路去分析即可。

本文主要参考《数据结构与算法之美》和维基百科。

评论