可能是最可爱的一文读懂系列：皮卡丘の复杂度分析指南

大数据文摘出品

来源：medium

编译：刘佳玮、李雷、陆震、高延、张秋玥、王缘缘、fuma、钱天培

啥是算法？

算法就是，程序猿懒得给你解释代码时，堵你嘴的东西。（这一步使用了XX算法。）

开个玩笑！不论什么算法，写出来之后你都得对它负责。

提到算法，就不得不提到复杂度分析——这也是程序猿面试跑不了的一关。

“复杂度分析”，说起来概念特别简单，可真分析起来，又常常让人手足无措。

今天，文摘菌就引用一些神奇宝贝的例子，给大家温故一下复杂度分析的概念，然后从易到难给大家介绍复杂度分析的常用方法。

文章分为5个部分。

1. 为什么要做“复杂度分析“？

2. 如何做“复杂度分析“？

3. 从排序算法说起

4. 递归算法分析

5. 如何选择最好的算法？

其中，1、2部分会对复杂度分析做简单介绍（熟悉复杂度分析基本概念的同学可以跳直部分3）。部分3会以排序算法为例，给出复杂度分析的经典案例。 部分4会重点分析递归算法，并介绍递归算法复杂度分析的两种方法：“递归树法”和更通用简洁的“主定理法”。最后，部分5会简要讨论，在实际情况中我们如何根据复杂度分析选择最好的算法。

为什么要做“复杂度分析”？

举个栗子来解释。

我们假设可爱的神奇宝贝们设立了一场锦标赛。每场比赛都有两个神奇宝贝参赛，胜者的等级会得到提升。

每次比赛，我们都会随意选出一个神奇宝贝，然后选出和它等级最接近的一位作为它的对手。

很简单嘛！在选取第一位神奇宝贝后，你可以将它的等级和其他所有神奇宝贝比较，这基本上是线性搜索。

但在比赛当天，我们假设有1000个口袋妖怪报名比赛！这个算法还可行吗？

可扩展性：绕也绕不过的问题

由上面的简单例子可见，可扩展性往往是是算法性能中不得不考虑的重要一环。

如何评估算法的可拓展性，我们就要讲到渐进分析。（通常，复杂度分析也就是我们这讲的渐进分析）

渐近分析是仅根据输入大小（N）来评估算法的性能，其中N可以非常大。渐进分析可以让你了解应用程序的局限性，因此对于衡量代码的性能非常重要。

例如，如果参与战斗的小宠物的数量是N，那么线性搜索算法的渐近复杂度是O（N）。如果你不知道这个符号是什么，请不要担心。我们马上就告诉你。

简单来说，你要询问N个小宠物他们的等级是什么，然后做出决定。想象一下，问所有1000个小宠物，这绝对是个累人的工作！

对于一台机器来说，O（N）可能并不坏，但对于一个看重响应速度和处理速度的网站而言，它可能不是最好的选择。

不考虑输入巨大的情况，你早晚会遇到可拓展性问题。

回到上面的例子。如果我们使用字典，或哈希表来查找具有相同排名的所有小宠物，我们就可以将算法时间复杂度降低到O（1）。

这就号像我们有个知晓所有神奇宝贝等级的经理人。我们只要问一下他，就能知道匹配答案了！

如何做“复杂度分析”？

让我们再来举一个渐进分析的例子吧！

我们假设皮卡丘正在寻找一个具有某种特殊能力的合作小精灵。皮卡丘开始逐一向所有小宠物询问他们的能力。这种方法被称为线性搜索，因为它是逐个线性地完成的。但是为了方便参考，让我们称之为“皮卡丘搜索”。

在上面的代码片段中，pokemons_list是参与锦标赛的所有神奇宝贝的列表。因此，该列表的大小为N。

皮卡丘搜索的运行时间分析：

1.第2步是一个循环，因此，其中的操作将重复N次。仅当步骤3中的条件为真时才执行步骤4。执行步骤4后，循环中断并返回结果。

2.如果步骤3花费的时间是常数级的，比如C1，那么for循环所用的总时间将是C1×N。

3.所有其他操作都是不受循环影响的常数时间操作，因此我们可以将所有这些操作作为C2的累计常量。

总运行时间f(N)=C1×N+C2，是一个与N相关的函数。

让我们把N放大。如果N的值非常非常大，该怎么办？你认为常数会有什么意义吗？

注意！在算法分析中，一个重要的想法是，忽略不太重要的部分。

例如，如果算法的运行时间渐近表示为10N²+ 2N + 5，则只有高阶项N²才有意义。这使得算法之间的比较更容易。

不同情况下的分析

每当输入不同，算法呈现的效果也不同。这意味着，我们需要讨论如何定义这种行为或算法的复杂性。

1.最佳情况〜绝对乐观。皮卡丘非常幸运，因为他接触的第一个精灵就拥有他正在寻找的特殊能力。

2.最差情况〜绝对悲观。皮卡丘不得不去拜访所有的小精灵，更令他沮丧的是，最后一个才拥有他想要的超能力。

3.普遍（平均）情况〜实事求是。皮卡丘现在已经长大，并且很有经验，他知道这一切都是时间和运气的问题。他估计在他遇到的前500个左右的精灵中找到超级口袋精灵的机会很高，他是对的。

上述三种情况都可以被用来分析算法。

“最佳情况复杂度”没有太大用处。它可以作为算法复杂度的下限值。如果你执意要用它来表示算法复杂度，那么你就只考虑了最佳情况。你必须得非常幸运，这样你的算法才能达到最佳情况。从实际意义上说，这对算法没有多大帮助。

“平均情况复杂度”通常很难计算，因为它需要你分析算法在各种输入上的性能，因此也没有被广泛的使用。

“最差情况复杂度”帮助你做好最坏的准备。在算法中，这种悲观主义是好的，因为它给出了复杂度的上限，这样你就知道你的算法有哪些限制！

复杂度分析工具

前面我们看到，皮卡丘搜索其他小精灵的总运行时间是N的函数，f(N)= C1.N + C2。让我们来了解一下有哪些工具可以用来表示运行时间，以便比较各算法。

Big O ?：哦，没错！它的发音就是这样，Big — Oh ！它是算法复杂度的上限。因此，它用于表示算法的最差情况。

它实际的意思是，不管输入是什么，算法的最大运行时间是多少。

这是使用最广泛的表达，因为它可以通过最差情况来分析算法。

C是常量。f（N）是运行时间函数，上界为g（N）。

对于皮卡丘的搜索，我们可以说f（N）或运行时间对于非常大的N，会向上达到C.g(N)，其中c是一个常量，g(N) = N。因此，O(N)表示皮卡丘搜索的渐近上界。

Big Omega（Ω）：与Big O表示法类似，Ω表示法用于定义算法性能的渐近下界。因此，它用于表示最佳情况场景。

Ω 下界本质上是在不考虑输入的情况下，算法执行所需的最短时间。

在实际情况中，这种表示法并不常用，因为研究最佳情况不能成为算法比较的正确衡量标准。

C是常量。f（N）是运行时间函数，其下界是g（N）。

对于皮卡丘的搜索，我们可以说f（N）或运行时间对于非常大的N，会向下达到C.g(N)，其中c为常量，g(N) = 1。因此Ω(1) 表示皮卡丘搜索的渐近下界。

Big Theta（Θ）：算法行为的严格约束，此符号定义函数的上界和下界。这称为紧确界，因为我们将运行时间限制在上下两个常量因子内。就像这样：

C1和C2是常量。f（N）是运行时间函数，g（N）是紧确界

每个算法可能有不同的最佳和最差情况。当两者相同时，我们倾向于使用Θ表示法。否则，最佳和最差情况需要被分别表示：

（a）对于很大的N值，最差情况的 f（N）受函数g(N) = N的限制。因此，紧确界复杂度将表示为Θ(N)。这意味着最坏的情况下皮卡丘的搜索时间是最少要C1⋅N，最多要C2⋅N。

（b）类似地，其最佳情况的紧确界复杂度是Θ(1)。

空间复杂度

我们之前一直在讨论时间复杂度。复杂度分析中的另一个重要概念是空间复杂度。顾名思义，它是指算法在N非常大的情况下占用多少硬盘空间或内存。

每当我们比较用于解决特定问题的各算法时，我们不仅仅关注时间复杂度，空间复杂度也是比较不同算法的重要方面。是的，可能目前我们的机器有大量可用内存，因此，多消耗些空间没什么影响。但是，我们不应该一直忽视它。

时空权衡

通常，你希望你的算法速度要快，而这样做可能最终会导致很糟糕的空间复杂度。

但有时，我们会牺牲一些时间来换取空间的优化。

在实际应用中，牺牲时间或者空间以换取另一方的优化被称为算法分析领域的“时空权衡”。

皮卡丘现在意识到了，他每隔一天就要寻找一个神奇宝贝。这意味着一遍又一遍地运行皮卡丘的搜索。嗯！他肯定厌倦了每天的大量重复工作。

为了帮助他加快搜索过程，我们决定使用哈希表。我们可以使用神奇宝贝的能力类型作为哈希表的键值。

如果我们需要找到具有某种特殊能力的小精灵，最坏的情况就是复杂度为O(1)，此时哈希表的查找时间是一个恒定值。

所以现在所需要的只是创建一个哈希表，然后使用它进行查找以降低整体运行时间！

但事情也不是这么简单，你可以看到这么做带来了空间成本。哈希表对每个Pokemon精灵会用一个条目来存储。因此，空间复杂度是O(N)。

选时间O(N) 空间O(1) ？还是时间O(1) 空间O(N)呢？

这样的选择取决于实际应用的需要。

如果我们有一个面向客户的应用程序，它的响应速度就不应该很慢。在这种情况下，优先考虑的是，无论使用多少空间，应用程序都应尽可能快速响应。但是，如果我们的程序受到可用空间的限制，则必须放弃快速响应来弥补空间的紧缺。

从排序算法说起

时间和空间的复杂性始终是紧密相连的。我们需要进行数学运算并且采用最好的方法。

现在，我们就来进行一些正儿八经的复杂度分析啦！

首先，皮卡丘想分析所有的排序算法。

让我们看看基本但关键的排序算法。假设要排序的输入数组pk_rank的大小为N.

如果你不熟悉下面提到的任何一种排序算法，建议你在阅读后面部分之前先了解一下它们。以下示例的目的不是为了解释不同的算法，而是去解释如何分析它们的时间和空间复杂度。

冒泡排序

冒泡排序是最简单的排序算法之一，它反复比较数组的相邻元素，如果它们乱序则交换位置。可以类比水里的泡沫最后会上升到水面上。随着数组元素的排序，它们会逐渐冒泡到数组中的正确位置。

就像皮卡丘玻璃杯中的气泡。

冒泡排序算法

时间复杂性：现在我们已经有了算法，再来分析它的时间和空间复杂性。我们可以清楚地从步骤2和3中看到算法中存在嵌套循环结构。第二个for循环的范围是N-1-i，表明它依赖于上一个循环。

当 i = 0时, 第二个for循环会被执行N-1次

当 i = 1时, 第二个for循环会被执行N-2次

当 i = 2时, 第二个for循环会被执行N-3次

当 i = N-1时, 第二个for循环会被执行0次

现在我们知道了冒泡排序算法在整个过程中的每一步所花费的时间。我们之前提到过，算法中有一个嵌套循环。对于第一个循环中的每个变量值，我们知道在第二个循环中所花费的时间。现在剩下的就是给这些加和。我们这样做：

S = N-1 + N-2 + N-3 + ... + 3 + 2 + 1 ~ N * (N+1) / 2 ~ N² + N（忽略常数）

如果你查看步骤4和步骤5，这些是常量时间操作。它们并没有真正增加时间复杂度（或者空间复杂性）。这意味着，我们有N²+ N次迭代，并且在每次迭代中，我们都执行了这些常量时间操作。

因此，冒泡排序算法的运行时间复杂度为C.（N²+ N），其中C是常量。因而我们可以说冒泡排序的最坏情况是时间复杂度为O（N²）。

这是一个很好的排序算法吗？我们还没有看过任何其他类似的算法来进行比较。但是，让我们看看这个算法需要多长时间来排序十亿个皮卡丘。

我们将计算留给你，结果是：排序十亿个皮卡丘（假设每个指令需要1毫秒执行）将需要大约31，790年。

空间复杂性：与该算法的时间复杂度相比，分析空间复杂度相对简单些。冒泡排序算法仅仅重复执行一个操作--交换数字。同时，它不使用任何外部存储器。它只是重新排列原始数组中的数字，因此，空间复杂度是个常量，即O（1）或者Θ（1）。

插入排序

你喜欢打牌吗？

在抓牌时，我们往往需要对牌组进行排序。插入排序的思想非常类似于对牌组进行排序。

比方说，你有几张按升序排序的卡牌。如果你被要求在右边插入另一张牌，同时要保证你手中的牌仍然是有序的。你会怎么做？

你可以从手中牌的最左侧或最右侧开始，将新牌与每张牌进行比较，从而找到合适的位置。

找到合适的位置后，你就可以在那里插入新抓的牌。

同样，如果有更多新牌，则对每张新卡重复相同的过程，同时要保证手中的卡是有序的。

插入排序原理相同。它从索引1开始（数组排序从0开始）并将每个元素视为一张新卡。然后，每个新元素就可以放置在已经排序的子阵列中的正确位置。

这里需要注意的重要事项是，给定一张新牌（即我们例子中索引为j的一个元素），手中的所有卡（即该索引前的所有元素）都已经排序完毕。

让我们看一下插入排序的正式算法。

时间复杂度：从步骤1和4开始，在for循环中有一个嵌套的while结构。 while循环运行j + 1次，其中j依赖于i。让我们看看j的值如何随着i的变化而变化。

当i=1时，j=0，while循环会被执行1次。

当i=2时，j=1，while循环会被执行2次。

当i=3时，j=2，while循环会被执行3次。

当i=N-1时，j=N-2，while循环会被执行N-1次。

现在我们知道插入排序算法在整个过程中的每一步所花费的时间（即迭代）。总时间是：

S = 1 + 2 + 3 + … N-2 + N-1 ~ N * (N+1) / 2 ~ N² + N（忽略常数）

步骤2到7是常量时间操作。它们并没有真正增加时间复杂度（或者空间复杂性）。这意味着，我们有N²+ N次迭代，并且在每次迭代中，我们都执行了这些常量时间操作。

因此，插入排序算法的运行时间复杂度是C.（N^2 + N），其中C是常量。因此，我们可以说插入排序的最坏情况是时间复杂度与冒泡排序的时间复杂度即O（N^2）相同。

空间复杂性：与该算法的时间复杂度相比，分析空间复杂度相对简单些。插入排序算法仅重新排列原始数组中的数字。同时，它根本不使用任何外部存储器。因此，空间复杂度是常量，即O（1）或者Θ（1）。

注意：基于渐近复杂度比较算法简单快捷。从理论分析来看，它是一个很好的衡量标准。但是从实践层面上看，如果两种算法具有相同的复杂性，也不一定意味着它们在实际场景中具有相同的表现性能。

在计算算法的渐近复杂度时，我们忽略所有常量因子和低阶项。

但是这些被忽略的值最终会增加算法的运行时间。

当数组几乎已经是按顺序排列好的时候，插入排序比冒泡排序快得多。对于每次遍历数组，冒泡排序必须一直走到数组的末尾并比较相邻数字的大小；另一方面，如果数组其实已经被排序，插入排序则会提前终止。你可以尝试在一个已经被排序的数组上执行这两个算法，并查看每个算法完成执行所需的迭代次数。

因此，当你在为自己的应用程序寻找最佳算法时，总是需要从许多不同方面进行分析。渐近分析肯定有助于淘汰较慢的算法，但更多的观察和更深入的见解有助于为你的应用找到最适合的算法。

合并排序

到目前为止，我们已经分析了两种最基本的排序算法。这些排序算法算是入门级必须介绍的，但它们具有高渐近复杂性，因此通常在实践中我们并不使用他们。

让我们来看一看更快、更实用的排序算法吧。

合并排序算法摒弃了我们在前两个算法中看到的嵌套循环结构化排序，采用了我们将在下面讨论的全新范例。

合并排序算法基于一种被称为各个击破的编程范式。这种编程范例基于一个非常简单的想法，并且在许多不同的算法中都很实用——包括合并排序。各个击破分为三个基本步骤：

• 划分：将一个大问题分解为更小的子问题。
• 攻克：最佳地解决子问题。
• 合并：最后，结合子问题的结果，找到原始大问题的解决方案。

让我们看一下合并排序算法是如何利用各个击破方法来解决问题的。

1.划分：该方法中的第一步是将给定的数组划分成两个大小相等的较小子数组。这其实还是挺有用的，因为我们现在只需要对两个只有原来元素数量一半的数组进行排序啦。

2.攻克：下一步是对较小的数组进行排序。这部分被称为攻克步骤，因为我们正在试图以最佳方式解决子问题。

3.结合：最后，我们看到原始数组的两半，他们都被排序好啦。现在我们必须以最佳方式来组合它们，以得到一整个排序好的数组。这其实是上面几步的组合步骤。

可是等等。这样就完了吗？

给定一个包含1000个元素的数组，如果我们将它分成2个相等的一半，每个500，我们仍然有很多元素要在数组（或子数组）中进行排序。

我们不应该将这两半进一步划分为4，以获得更短的子阵列吗？

当然应该啦！

我们递归地将数组划分为较小的数组们，并对它们进行排序与合并以重新获得原始数组。

这实质上意味着我们将例如1000的数组分成两半，每组500。然后我们进一步将这两半分成4个部分，每部分250个，依此类推。如果你无法在复杂性分析方面直观地考虑所有这些问题，请不要担心。我们很快就会谈到这一点。

我们来看看合并排序算法。该算法分为两个函数，一个递归函数对给定数组的两半分别进行排序，另一个则将两半合并在一起。

我们将首先分析合并（merge）函数的复杂性，然后分析合并排序（merge_sort）函数。

合并两个排好序的数组

上面的函数简单地将数组的两个已排序的一半合并为一个已排序的数组。用索引来表示两半的话就是，左半部分来自[left, mid]，右半部分来自[mid + 1, right]。

第2-3步将元素从原始数组复制到临时缓冲区，我们使用此缓冲区进行合并。已排序的元素将被复制回原始数组。由于我们会遍历数组的某个部分，假设该数组有N个元素的话，该操作的时间复杂度为O(N)。

第5步是一个while循环，迭代两个子数组中较短的一个。这个while循环和之后第13与14步内的循环涵盖了两个子阵列的所有元素。因此，他们的时间复杂度是O(N)。

这意味着合并步骤算法的时间复杂度是线性的。

合并排序的总体复杂性取决于调用合并函数的次数。

让我们继续看看原始的合并排序（merge_sort）函数。

第4步在数组的左半部分调用该函数（merge_sort）。

第5步在数组的右半部分调用该函数（merge_sort）。

然后第6步最后调用合并（merge）函数将两半结合起来。

呃。一个函数调用自己？????

如何计算它的复杂性？

目前为止我们已经讨论过循环分析。然而，许多算法（比如合并排序）本质上是递归的。当我们分析它们时，我们得到时间复杂度上的递归关系。我们获得了计算输入大小为N的算法时间复杂度的函数；它依赖于N，以及小于N的输入的运行时间。

递归算法分析

主要有两种方法来分析递归关系的复杂性：

1.使用递归树

2.主定理方法

递归树分析

这是分析递归关系复杂性最直观的方式。本质上，我们可以以递归树的形式可视化递归关系。

可视化有助于了解算法在每个步骤（读取级别）完成的工作量。总结在每个级别完成的工作能够告诉我们算法的整体复杂性。

在我们画出合并排序算法的递归树之前，让我们首先看一下它的递归关系。

T（N）= 2T（N / 2）+ O（N）

用T(N)表示对由N元素组成的数组进行排序所完成的工作量（或所花费的时间）。上述关系表明，所花费的总时间等于将数组的两半分别排序所花费的时间加上将其合并所花费的时间。我们已经知道合并两半数组所花费的时间了——O(N)。

我们可以写出递归关系如下：

T（N） = 2T（N / 2）+ O（N）

T（N / 2）= 2T（N / 4）+ O（N / 2）

T（N / 4）= 2T（N / 8）+ O（N / 4）

......

以树的形式可视化更容易。树中的每个节点都包含两个分支，因为在给定每个单个问题时我们都有两个不同的子问题。让我们看一下合并排序的递归树。

用于归并排序的递归树

每一个节点表示一个子问题，每个节点上的数值表示解决该问题需要花费的工作量。根节点表示的就是初始问题。

在我们的递归树中，每个非叶节点有2个子节点，而且标有子所划分处的子问题数量。从归并排序算法中，我们可以可以看到在进行每一步递归的时候，给定的数组会被等分为两份。

因此，为了分析归并排序的复杂度，我们需要弄清楚两件重要的事。

1.我们需要知道树结构中的每个层级(level)需完成的工作量。

2. 我们需要知道树的总层数，也就是大家通常所说的树的高度。

首先，我们要计算一下递归树的高度。从上图所示的递归树中，我们能看到每个非叶节点都分位两个节点。因此，这就是一个完整的二叉树。

我们会一直拆分数值直到子数组中只剩下一个元素(也就是最底层)，这时我们就可以不用排序直接返回了。

在我们的二元递归树的第一层，有一个有N个元素组成的问题。其下一层由两个子问题(需要进行排序的数组)构成，每个子问题都有N/2个元素。

我们真正关心的并不是有多少子问题，我们只想知道每个子问题的大小，因为在树结构里，同一层内的子问题都有一样的大小。

节点内元素的数量按照2的次方递减。所以按上述的模式可以表示为：

N = 2^X X = log_2(N)

这表示树的高度为log_2(N)(N以2为底求对数)。那就让我们看一下算法在每一步需要完成的工作量。

我们定义T(N)为对含有N个元素的数组进行排序所需的工作量。

T(N) = 2T(N / 2) + O(N)

这算式表示树结构中的第一层的工作量为O(N)， 其余的工作量2T(N / 2)在下一层完成。在下一级，如上图所示，需完成的工作量是2 * O(N / 2) = O(N)。类似地，在第三层要完成的工作量就是4 * O(N / 4) = O(N)。

令人惊讶的是，该算法在每层上的工作量是相同的，且都等于O(N)，这是归并操作所消耗的时间。因此，可以用层数来定义总体的时间复杂度数。

如我们前面计算的那样，递归树的层数是log(N)，因此，归并排序的时间复杂度就是O(Nlog(N))。

很好，我们掌握了一种用递归树形式进行渐进分析的方法。这是种有趣的方法，可以让我们很直观地认识递归关系的复杂度。虽然去绘制完整的递归树是不可行的，但递归树有助于我们建立对递归关系的理解。

主定理方法

我们研究了基于递归树的分析方法，以实现对递归进行渐进分析。但是，如前文所述，每次为了计算复杂度去绘制递归树是不可行的。

归并排序递归只是将问题(数组)划分为两个子问题(子数组)。但是，当有算法要把问题分成100份子问题时，我们要怎么分析呢，显然不能通过绘制递归树的方式。

因此，我们要用一种更直接的方式来分析递归关系的复杂度。通过这种方式，我们不需要实际地绘制递归树，而且这种方式也是基于和递归树一样的概念上。

主定理方法这时就强势登场了，它也是基于递归树方法。该方法能应用于三种不同的场景，基本上也就是涵盖了大部分的递归关系。在展示案例之前，我们先看看通用递归关系的递归树：

• T(n) = a T(n / b) + f(n)
• n 是总问题的大小。
• a 是递归关系中子问题的数量。
• n/b 每子问题的的大小(假设子问题大小相同)
• f(n) 表示调用递归之外的工作成本，包括将问题划分为较小子问题的成本及合并子问题解决方案的成本。

想理解主定理方法，有两点最重要，分别是算法在根节点的工作量和在叶节点工作量。

根节点工作量相对点简单，就是f(n)。叶节点的工作量取决于其所在树上的高度。

树的高度为log_b(n)，也就是以b为底取n的对数。这和归并排序的递归树道理一样，而在归并排序中b就是2。在任意层l的节点数量就是a^l，所以最后一层的叶节点数可由如下算式所得：

a^{log_b(n)} = n ^ log_b(a) nodes.

假设在末层完成每个子问题所需的工作量为Θ(1)，因此在叶节点处完成的工作量就是n ^ log_b(a)。

如果你认真观察通用递归关系，你会发现如下两个成分：

1.分部步骤??(?/?)算子，这部分会不断复制并不断乘以值越来越小的本身。

2.治理步骤?(?) 算子，这部分会把迷你部分聚集在一起。

这两股力量似乎在相互对抗，这样一来，他们想控制算法的总工作量，从而控制整体时间复杂度。

谁会占主导呢？我们需要分三种情况讨论

情况1(分部步骤获胜)

如果f(n) = Θ(n^c)，使得c < log_b(a)，那么可得出T(n) = Θ(n^log_b(a))。其中f(n)是根节点处工作量，n ^ log_b(a)是叶节点的工作量。

如果叶节点的工作量是多项式形式的，那计算结果就是叶节点的工作量。

e.g. T(n) = 8 T(n / 2) + 1000 n^2

在这个例子中，a = 8，b = 2，f（n）= O（n ^ 2）

因此， c = 2且log_b（a）= log_2（8）= 3

显然2 <3， 并且很容易看出这适用于Master方法的案例1。这意味着，在树叶处完成的工作量渐近地高于在根处完成的工作量。因此，该递归关系的复杂度是 Θ（n ^ log_2（8））=Θ（n ^ 3）。

案例2（治理步骤获胜）

如果 f（n）=Θ（n ^ c） 使得 c> log_b（a） ，则 T（n）=Θ（f（n）） 。如果在根节点上完成的工作渐进式更多，那么我们的最终复杂度就是根节点的复杂度。

我们并不关心较低级别的工作量，因为最大的多项式项依赖于控制算法复杂度的n。因此，所有较低级别上的工作可以被忽略。

例如T（n）= 2T（n / 2）+ n ^ 2

如果在主定理方法中适合这种递归关系，我们可以得到：

a = 2, b = 2, and f(n) = O(n^2)

因此， c = 2且log_b（a）= log_2（2）= 1

显然2> 1，因此这符合Master方法的情况2，其中大部分工作是在递归树的根处完成的，这就是为什么 Θ（f（n））控制算法的复杂度的原因。因此，该递归关系的时间复杂度是Θ（n ^ 2）。

案例3 （平局！）

如果 f（n）=Θ（n ^ c） 使得 c = log_b（a） ，则 T（n）=Θ（n ^ c * log（n））。最后一种情况是，在叶上完成的工作和在根处完成的工作之间打成平局。

在这种情况下，治理和分步骤同样占主导地位，因此完成的工作总量等于在任何级别完成的工作量*树的高度。

例如T（n）= 2T（n / 2）+ O（n）

等等，这不就是归并排序嘛！

对!这就是归并排序算法的复杂度。如果我们在主定理方法中采用归并排序的递归关系，我们得到：

a = 2，b = 2，f（n）= O（n ^ 2）

因此， c = 1 = log_2（2）

这符合上述案例3中的标准。通过上面的数字可以证明所有级别的工作量都将相等。因此，时间复杂度等于在任何级别的工作量*所有级别数（或者是树的高度）。

我们使用两种不同的方法分析了归并排序算法的时间复杂度，即递归树和主定理法。因为归并排序算法是一种递归算法，我们之前看到的用于解决循环问题的经典渐近分析方法在这里没用到。

空间复杂度：对于空间复杂度，我们不必使用任何复杂的技术，因此分析更简单。在归并排序算法中占用数据结构的一个主要空间是合并过程中使用的临时缓冲区。这个数组被初始化一次，此数组的大小是 N。占用空间的另一种数据结构是递归堆栈。实质上，递归调用的总数决定了递归堆栈的大小。正如我们在递归树表示中看到的那样，归并排序调用的次数基本上是递归树的高度。

递归树的高度是 log_2（N） ，因此，递归堆栈的最大也就是log_2（N） 。

因此，归并排序的总空间复杂度将是 N + log_2（N）= O（N） 。

二进制搜索

还记得吗，皮卡丘想要寻找特定能力的神奇宝贝。小皮卡丘有1000 个小伙伴，他必须找到一个具有特定能力的神奇宝贝。是的，皮卡丘对他的对手非常挑剔。

他的要求一天一个变，每当他的要求发生变化时，他肯定不能去检查每一个神奇宝贝，也就是说他不能通过执行线性搜索来找到他正在寻找的目标。

我们之前提到使用哈希表来存储神奇宝贝的数据，用它们的能力作为key，神奇宝贝本身作为value。这会降低搜索的复杂度至O（1）即恒定时间。

然而，在考虑到有N个神奇宝贝可用的情况下，这会用到额外的空间使搜索操作的空间复杂度提高到 O（N） 。在这种情况下，N将是1000。如果皮卡丘没有这些额外的空间，但仍然想加快搜索过程，那要怎么办呢？

没错！皮卡丘可以利用他对排序算法的深刻了解，想出一种比慢速线性搜索更快的搜索策略。

皮卡丘决定向他的好朋友代欧奇希斯寻求帮助。代欧奇希斯可以帮助皮卡丘根据宝贝的能力值重新排列神奇宝贝列表。

代欧奇希斯使用快速排序算法，而不是传统的排序算法对神奇宝贝排序。

这么一来，他没有使用任何额外的空间，并且排序 N个神奇宝贝所花费的时间与归并排序算法一样。

之后，皮卡丘非常聪明地提出了一种搜索策略，利用了神奇宝贝列表的排序特性。

这种新的策略/算法被称为二进制搜索 算法。（ 注：排序是运行二进制搜索的前提条件，一旦列表被排序后，皮卡丘可以在此排序列表上多次运行二进制搜索）。

让我们看看这个算法的代码，然后分析它的复杂性。

显然，该算法的本质是递归。我们尝试用新学到的技巧来分析二进制搜索算法的时间复杂度。这两个变量l和r基本上定义了数组中我们必须搜索对给定要素x的部分 。

如果我们看一下算法，它所做的一切就是将输入数组的搜索部分分成两半。除了根据某种条件进行递归调用之外，它实际上并没有做任何事情。那么，让我们快速查看二进制搜索算法的递归关系。

T(n) = T(n / 2) + O(1)

这看起来好像是一个非常简单的递归关系。首先让我们尝试分析递归树并从中得出复杂性，然后我们将使用主定理方法，看看三种情况中哪一种适合这种递归。

哇！这种二进制搜索算法非常快。它比线性搜索快得多。这对我们可爱的好朋友皮卡丘来说意味着，在1000只小精灵中，他最多只需要去询问其中的10个，就可以找到他特殊的口袋妖怪。

现在让我们看看如何采用更“公式化”的方法进行递归复杂度分析。Master方法在这种情况下对我们有所帮助。通用主方法的递归关系是

T(n) = a T(n / b) + f(n)

而对于我们的二进制搜索算法，我们有

T(n) = T(n / 2) + O(1) f(n) = O(n^0), hence c = 0 a = 1 b = 2 c = 0

对于Master定理来说有3种不同的情况，而c和 log_b（a）是其中的影响因素。在我们的例子中，0 =log_2（1）即0 = 0的时候，二分搜索算法符合主定理的情况3，因此T(n) = Θ(n^0 log(n)) = Θ(log(n)

如何选择最好的算法？

在本文中，我们介绍了复杂性分析的概念，它是算法设计和开发的重要部分。我们看到为什么分析算法的复杂性很重要，以及它如何直接影响我们的最终决策。我们甚至看到了一些有效和正确分析这种复杂性的优秀技术，以便及时做出明智的决策。然而，问题出现了，

鉴于我所知道的两种算法的时间和空间复杂性，我该如何选择最终使用哪种算法？有黄金法则吗？

很遗憾，答案是，没有。

没有黄金法则可以帮助你决定使用哪种算法。这完全取决于很多外部因素。看看以下几种情况的例子吧！

空间无约束

如果你有两个算法A和B，并且你想要决定使用哪个算法，除了时间复杂度之外，空间复杂度也会成为一个重要因素。

但是，考虑到空间不是你所关心的问题，最好采用能够在更多空间的情况下进一步降低时间复杂度的算法。

例如，Counting Sort是一种线性时间排序算法，但它在很大程度上取决于可用空间量。确切地说，它可以处理的数字范围取决于可用空间的大小。给定无限空间，你最好使用Counting Sort算法对大量数字进行排序。

亚秒级延迟要求和可用空间有限

如果你发现自己处于这种情况，那么深入了解算法在许多不同输入上的性能变得非常重要，尤其是你期望算法在你的应用程序中使用的输入类型。

例如，我们有两种排序算法：冒泡排序和插入排序，你要在其中决定使用哪一种用于根据用户年龄对用户列表进行排序。你分析了预期的输入类型，并且你发现输入数组几乎已经排序。在这种情况下，最好采用插入排序。

等等，为什么有人会在现实中用插入排序或者冒泡排序？

的确，很多人认为这些算法仅用于教育目的而未在任何真实场景中使用。但实际并非如此。

比如Python中的sort（）功能。它就使用了基于插入排序和归并排序的混合算法，称为Tim Sort算法。

确实，插入排序可能对非常大的输入没有用，正如我们从其多项式时间复杂度中看到的那样。然而，它却能迅速处理几乎排好序的数组，这正是它在Timsort算法中使用的原因。

简而言之，不同算法之间不会有明确的黑白划分。

算法的属性，如它们的时间和空间复杂性，都是非常重要的考虑因素。算法使用的输入大小以及可能存在的任何其他约束也有可能产生影响。

考虑到所有这些因素，我们才能做出明智的决定！

相关报道：

https://medium.freecodecamp.org/asymptotic-analysis-explained-with-pok%C3%A9mon-a-deep-dive-into-complexity-analysis-8bf4396804e0