1.3　复杂度分析

所有的数据结构教程都会把复杂度分析放在前面来讲，这不仅是因为复杂度分析是基础，更因为它们真的非常重要。学会了复杂度分析，才能够对算法进行正确分析，从而写出复杂度更优的算法。如果你对一种算法的复杂度推导很熟悉，就意味着你已经完全理解了这个算法。

算法的复杂度分析分为两个方面：时间复杂度和空间复杂度，通常我们更加关注前者。两者的分析方法类似，并且在大多数情况下，对空间复杂度的分析更为容易，本章将围绕如何求时间复杂度展开。

通常来说，算法决定了程序的性能，性能可以从完成同一项任务所使用的时间的长短、占用内存的大小两个方面去考量。内存大小可以清晰地用数字进行量化，但是运行时长，由于不同计算机的性能不同，执行时间也会不同，甚至有可能有数倍的差距，那么究竟应该如何衡量程序运行时间的长短呢？

《计算机程序设计艺术》的作者高德纳（Donald Knuth）提出了一种方法，这种方法的核心思想很简单，就是一个程序的运行时间主要和两个因素有关：

1.执行每条语句的耗时。

2.执行每条语句的频率。

前者取决于硬件，后者取决于算法本身和程序的输入。在相同的硬件环境下，不同算法的执行时间只取决于语句的执行频率，因此可以将对执行时间的关注进一步简化为对执行频率的关注。那么如何统计算法执行每条语句的频率呢？我们举个例子来说明。

如下是一段计算从1累加到n的代码，使用了一层循环，并且借助了一个变量res来存储计算结果。

上述代码会执行n次循环体的内容，假设每一次执行时间都是常数，不妨假设其执行时间是x，res=0和return res的执行时间分别为y和z，那么总的执行时间就等于nx+y+z。如果粗略地将x、y和z都看成一样的，那么可以得出总时间为(n +2)x，如下图所示。

可以明显看出，算法的运行时间和数据的规模成正比。

随着数据规模的不断扩大，即n的值成百上千倍地变大，从渐进的趋势上讲，我们常常忽略较小项，如上面的2x，而仅保留最大项，如上面的nx，这样可以大大减少分析的工作量，因此这种复杂度分析方法也被称为渐进复杂度分析。实际上，这在现实中也很常见，即程序运行时间往往取决于其中一小部分指令。

基于以上思想，产生了大O表示法，它是一种描述算法性能的记法，这种描述和编译系统、机器结构、处理器的快慢等因素无关。假设参数n表示数据的规模，这里的O表示量级（order），比如说“二分查找的时间复杂度是O(logn)”，表示它需要“通过logn量级的操作去查找一个规模为n的数据结构”。这种估测对算法的理论分析和比较是非常有价值的，我们可以快速地对算法效率进行大致的估算。

例如，一个拥有较小系数的O(n2)算法在规模n较小的情况下可能比一个高系数的O(n)算法运行得更快，但是随着n变得足够大以后，具有较慢上升趋势的算法必然运行得更快，因此在采用大O表示法表示复杂度时，可以忽略系数，这也是我们可以忽略不同性能的计算机执行时间差异的原因，因为你可以把不同性能的计算机性能差异看成系数的差异。

除此之外，我们还应该区分算法的最好情况、最坏情况和平均情况，更多关于复杂度分析的理论知识，读者可以阅读《算法》（第4版）中 1.4 节算法分析的内容获得。

接下来，我们介绍几种常见的复杂度以及其对应的分析方法。

1.3.1　迭代复杂度分析

下面介绍几种常见的时间复杂度，绝大多数算法的时间复杂度都是如下中的一种。

●　第1类是常数阶，即O(1)。

只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是O(1)。

●　第2类是多项式，例如O(n)、O(n2)、O(n3)。

判断一个算法是不是属于这种时间复杂度的一个简单方法是关注循环执行次数最多的那一段代码，这段代码执行次数对应n的量级，就是整个算法的时间复杂度。如果是一层n的循环，那么时间复杂度就是O(n)；如果嵌套了两层n的循环，那么时间复杂度就是O(n2)，以此类推。

上面的代码进行了一层循环，那么时间复杂度就是O(n)。实际情况可能会比较复杂，需要结合具体的代码逻辑进行判断，代码示例如下。

这是力扣（LeetCode）第739题每日温度中使用单调栈解法的代码。外层for循环和内层while循环嵌套，执行次数最多的代码很显然是while 循环内部的语句，那是不是说该算法的时间复杂度就是O(n2)呢？其实不是，该算法的时间复杂度为O(n)，其中n为数组长度。原因在于，内层while循环执行的总次数是n，究其根本是因为对于数组T中的每一项来说，其仅会进栈一次并出栈一次，因此内存代码执行的总次数和数组长度线性相关。

●　第3类是对数阶：O(logn)和O(nlogn)。

对数阶同样是一种非常常见的时间复杂度，多见于二分查找和一些排序算法。

二分查找的时间复杂度通常是O(logn)，一些基于比较的排序算法的时间复杂度可以达到O(nlogn)，典型的有快速排序、归并排序。

上面的代码是一个典型的二分查找，由于每次循环都可以将问题的规模缩减一半，其时间复杂度是O(logn)。

●　第4类是指数阶O(2n)。

指数的增长非常恐怖，一个指数阶的算法通常是不可用的，或者存在优化的空间。一个典型的例子是fibonacci数列的递归实现版本。

可以看出fibonacci(n)等价于fibonacci(n-1)+fibonacci(n-2)。这一过程可以持续下去，即fibonacci(n-1)等价于fibonacci(n-2)+fibonacci(n-3 )……如果你把上述每一个计算过程看成树的一个节点，那么整个计算过程就像一棵很大的树。一个节点分裂为2个节点，2个节点分裂为4个节点。

算法的时间复杂度和图中树的节点数同阶，而树的节点数的数量级为O(2n)，因此这个算法的时间复杂度是 O(2n)。可以看出其中有许多重复的计算，可以通过存储记忆的方式进行优化。

●　第5类是阶乘复杂度O(n!)。

旅行商问题（Travelling Salesman Problem，TSP）是著名的NP问题，暴力的解法可以枚举点的排列，这种算法的时间复杂度是O(n!)。另外一个比较典型的问题是全排列。

如下代码是力扣（LeetCode）第46题全排列的解法（这里使用了18.2节提供的回溯模板）。

我们来简单分析一下上面代码的执行过程，这样可以帮助你理解O(n!)是如何计算出来的。

为了描述方便，假设最终生成的具体的排列是a，所有排列形成的全排列是A。上述计算全排列的过程，可以看成如下步骤。

●　先选择a的第1个元素。

●　再选择a的第2个元素。

●　……

●　直到a中的所有元素都被选择，即a的长度和nums的长度相同。

上面的过程用图来表示，则如下所示。

实际上，可以将其看作一个决策树。树的每一个非叶子节点都要进行选择，选择的范围是其子节点。不考虑内部代码，只考虑回溯过程，总的计算次数就是节点总数。不难得出如下结论。

●　第1层（不考虑开始的那一层）节点总数为n，其中n为nums数组的长度（下同）。

●　第2层节点总数为n×(n-1)。

●　……

●　第n层节点总数为n×(n-1)…×1。

因此节点总数应该是n+n×(n-1)+n×(n-1)×(n-2)+…+n×(n-1)…×1。忽略低次项，得到n×(n-1)…×1，很明显这就是O(n!)，因此上面全排列的代码时间复杂度大致是O(n!)。

1.3.2　递归算法复杂度分析

与迭代相比，递归在书写上有很大的优势，本书也大量使用了递归解法，因此掌握递归的时间复杂度分析也非常重要。接下来，我们来看一下如何分析递归算法的时间复杂度。

递归算法采用的是分治的思想，把一个大问题分解为若干个相似的子问题求解。识别子问题之间的递归公式是进行递归复杂度分析的前提和根本。这里介绍两种方法来分析递归的时间复杂度，分别是递归树法和代入法。

递归树法

递归树分析是一种将递归过程描述成树结构的方法。初始树只有一个节点，随着每一次递归，树的深度加1。每一层的节点数取决于具体的场景。

在得到递归树后，将树每层中的节点求和，然后将所有层的节点求和，就大致可以得出树的总节点数n了。而整个算法的基本操作数等于树上每一个节点的基本操作数t乘以树的总节点个数n。

以归并排序为例，它是一个典型的分治算法。其基本过程分成两个阶段：分与合。其中分的过程采用自顶向下的方式，每次将问题规模缩小一半，直到问题规模缩小到寻常情况，即可以被直观解决的情况。合的过程恰好相反，采用自底向上的方式，将问题一步步解决，直到还原到原问题规模。

如果你将这两个过程化成递归树的话，就会发现这两个过程递归树的深度都是logn。而每一层的节点数都是n，也就是说总节点数是nlogn，而节点的基本操作数是常数（这一点读者可以通过归并代码发现），因此总的算法时间复杂度为O(nlogn)。

代入法

这种分析方法需要一点数学知识，相对来说没有那么直观，这种方法的入手点在于递归公式。比如有如下递归公式：T(n)=T(n-1)+T(0)，如何求解其时间复杂度？

T(n)=T(n-1)+T(0)指的是规模为n的问题，可以转化为规模为n-1的子问题和一个常数的操作。

我们来尝试代入，就像高中数学那样。

T(n)=T(n-1)+T(0)

=T(n-2)+T(0)+T(0)

=T(n-3)+T(0)+T(0)+T(0)

=T(0)+…+T(0)+T(0)+T(0)

=n×T(0)

可以得出其时间复杂度为O(n)。

趁热打铁，再来一个稍微复杂一点的：T(n)=2×T(n/2)+n，只要模仿上述过程进行代入操作即可。

T(n)=2×T(n/2)+n指的是规模为n的问题，可以转化为规模为n/2的子问题和一个n的操作。

T(n)=2×T(n/2)+n

=4×T(n/4)+2×n/2+n

=…

=…4×n/4+2×n/2+n

也就是T(n)约等于logn个n相加，因此时间复杂度大致为O(nlogn)。当你熟练了上面的分析过程之后，下次看到这样的递推公式，甚至不需要分析，就会立马想到对应的复杂度，这就是量变引起质变的过程。

除了上面提到的常见方法，进行复杂度分析的方法还有很多，比如数学归纳法，感兴趣的读者可以参考《算法设计与分析》和《算法导论》相关章节去学习、了解。

需要注意的是，递归算法的调用栈空间经常被大家忽略，其实我们可以将递归算法看作使用了栈的迭代算法，这个栈就是递归中的调用栈，因此计算递归的空间复杂度需要加上开辟的栈空间。一个递归算法的调用栈大小取决于递归的最大深度。如果你能画出递归树的话，这其实就是递归树的最大深度。

最后给大家列举几种常见的时间复杂度的趋势对比图，手绘图并不精确，但也能直观地反映出不同时间复杂度的趋势变化。我们也会在20.1节看限制条件部分进一步介绍关于复杂度的实用技巧。