1.5　性能分析

算法的性能分析是算法设计的重要部分。估计算法性能的方法之一是分析算法的复杂度。

复杂度理论研究算法的复杂程度。任何有用的算法应该具备以下三个关键特征：

• 算法应该是正确的。算法如果无法给你正确的答案，则对你毫无用处。
• 好算法应该是易懂的。如果世界上最好的算法对你来说太复杂，你无法在计算机上实现，则它对你也毫无用处。
• 好算法应该是高效的。即使算法能产生正确结果，但是如果它需要花费一千年或者10亿TB的内存，那么它的用处也不大。

有两种方法用于量化分析算法的复杂度：

• 空间复杂度分析：估计算法运行对内存的需求。
• 时间复杂度分析：估计算法的运行时间。

1.5.1　空间复杂度分析

空间复杂度分析就是估计算法在处理输入数据时所需的内存量。在处理输入数据的同时，算法需要在内存中存储一些临时的数据结构。算法的设计方式将会影响这些数据结构的数量、类型和规模。在分布式计算时代，需要处理的数据量越来越大，空间复杂度分析变得日益重要。这些数据结构的规模、类型和数量将决定对于底层硬件的内存需求。分布式计算中使用的现代内存数据结构——如弹性分布式数据集（Resilient Distributed Dataset，RDD）——需要高效的资源分配机制，使其能够感知算法在不同执行阶段的内存需求。

空间复杂度分析是高效算法设计中必须完成的工作。如果在设计特定算法时没有展开空间复杂度分析，临时数据结构可用的内存不足，则可能会触发不必要的磁盘溢出，从而大大影响算法的性能和效率。

本章仅深入讨论时间复杂度。空间复杂度将在第13章中进行更详细的讨论，届时将对运行时内存需求比较复杂的大规模分布式算法进行处理。

1.5.2　时间复杂度分析

时间复杂度分析就是依据算法结构来估计算法完成其指定工作所需的时间。与空间复杂度不同，时间复杂度并不取决于运行算法的任何硬件设施，而是完全取决于算法本身的结构。时间复杂度分析的总体目标是试图回答下列重要问题：算法是否具有良好的可扩展性？算法在处理更大规模数据集时性能如何变化？

为回答这些问题，我们需要确定数据规模的增加对算法性能的影响，并确保设计的算法不仅准确，而且具有良好的可扩展性。在当今“大数据”的世界里，算法处理更大规模数据集时的性能变得越来越重要。

在很多情况下，设计算法的方法可能不止一种。此时，时间复杂度分析的目的如下：

“给定某个问题和多种算法，从时间效率来看，使用哪种算法效率最高？”

计算算法的时间复杂度有以下两种基本方法：

• 实现算法后的分析方法：这种方法先分别实现各种候选算法，再对其性能进行比较。
• 实现算法前的理论方法：这种方法在运行算法前用数学方法近似计算每个算法的性能。

理论方法的优点是它仅依赖于算法本身的结构，而不依赖于将用于运行该算法的实际硬件、运行算法时所选择的相关软件和用于实现该算法的编程语言。

1.5.3　性能评估

典型算法的性能都取决于作为输入提供给它的数据的类型。例如，如果在待求解问题中数据已经排序，则该算法执行的速度可能会快得惊人。如果用排序后的输入作为基准来对特定算法进行测试，则将得到不真实的、过好的性能测试结果，而这个结果在大多数情况下并不能够反映算法的实际性能。为了处理算法对输入数据的这种依赖性，我们在进行性能分析时需要考虑各种不同情况。

最好复杂度

在最好复杂度中，输入数据经过组织，能够得到算法的最佳性能。最好复杂度分析得出算法性能的上界。

最坏复杂度

评估算法性能的第二种方法是尝试找到算法在给定条件下完成工作所需的最大可能时间。最坏复杂度分析非常有用，因为我们可以保证无论在何种条件下算法的性能总是优于所得的分析结果。在评估算法在处理更大规模数据集的复杂问题时，最坏复杂度分析特别有用。最坏复杂度给出了算法性能的下界。

平均复杂度

平均复杂度分析先将各种可能的输入划分为不同的组，然后从每组中选择具有代表性的一个输入来分析算法性能，最后计算出算法在各组输入上的平均性能。

平均复杂度并不总是准确结果，因为它需要考虑算法输入的所有不同组合和可能性，但这并不总是容易做到的。

1.5.4　选择算法

你怎么知道哪种方案更好？你怎么知道哪种算法运行得更快？时间复杂度和大O记号（本章后面会讨论）为回答这种问题提供了有效手段。

为了理解它的作用，我们举一个简单的例子：对一个数字列表进行排序。有几种可用的算法可以完成这项工作，问题是如何选择合适的算法。

首先，易于观察到的事实是，如果列表中数字为数不多，则我们选择哪种算法来排序数字列表根本无关紧要。例如，如果列表中只有10个数字（n=10），则我们选择哪种算法均不要紧，因为即使是设计得非常糟糕的算法，所花费的时间可能也不会超过几微秒。但是，如果列表规模高达100万，则选择合适的算法就会产生区别。一个写得很差的算法甚至可能需要几个小时才能完成列表排序任务，而一个设计较好的算法则可能仅用几秒就完成了任务。因此，在大规模输入数据集上，投入时间和精力展开性能分析，选择合理设计的算法来高效地完成要求的任务是非常有意义的。

1.5.5　大O记号

大O记号用于量化表示各种算法在输入规模增长时的性能，它是最坏复杂度分析中最常用的方法之一。下面讨论不同种类的大O记号。

常数时间复杂度（O(1)）

如果算法运行时间是独立于输入数据规模的相同值，则称其运行时间是常数时间，表示为O(1)。例如，考虑访问数组的第n个元素，无论数组的规模多大，花费常数时间即可获得结果。再如，下面的函数以复杂度O(1)返回数组的第一个元素：

其输出结果显示为图1-7。

• 使用push向栈内添加新的元素，或使用pop从栈中删除元素。无论栈的规模多大，添加和删除元素都花费常数时间。
• 访问哈希表中的元素（参见第2章的相关讨论）。
• 桶排序（参见第2章的相关讨论）。

线性时间复杂度（O(n)）

如果算法的执行时间与输入规模成正比，则称该算法具有线性时间复杂度，表示为O(n)。例如，考虑下面对一维数据结构中所有元素求和的算法：

注意算法的主循环。算法中主循环的迭代次数随着n值的增加而线性增加，导致了O(n)的复杂度，图1-8展示了算法的运行实例。

其他一些数组操作的例子如下：

• 查找元素
• 找出数组中所有元素的最小值

平方时间复杂度（O(n2)）

如果算法的执行时间与输入规模的平方成正比，则称该算法的运行时间为平方时间。例如，考虑下面对二维数组求和的简单函数：

注意，在内层循环嵌套外层主循环中，这种嵌套结构使得前面代码的时间复杂度为O(n2)（如图1-9所示）。

另一个例子是冒泡排序算法（参见第2章的相关讨论）。

对数时间复杂度（O(log n)）

如果算法的执行时间与输入规模的对数成正比，则称该算法的运行时间为对数时间。在时间复杂度为O(log n)的算法中，随着算法的每一轮迭代，输入规模都会以常数倍数递减。例如，二分查找是对数时间复杂度，该算法用于从一维数据结构（如Python列表）中查找特定元素，它要求数据结构内的元素按降序进行排序。下面的代码将二分查找算法实现为一个名为searchBinary的函数：

主循环利用了列表有序这一事实。算法中每轮迭代都将列表二等分，直到得到结果（如图1-10所示）。

定义完函数后，图1-10的第11行和第12行中通过查找特定元素对其进行了测试。二分查找算法将在第3章中进一步讨论。

注意，在所介绍的四种类型的大O记号中，O(n2)表示最差性能，O(log n)表示最佳性能。事实上，O(log n)可以视为任何算法性能的黄金标准（尽管并非总是能够达到）。另一方面，O(n2)并不像O(n3)那样糟糕，但由于时间复杂度限制了它们实际可以处理的数据规模，因此属于这类时间复杂度的算法仍然不能用于大数据。

降低算法复杂度的一种方法是在算法的准确度上进行折中，从而得到一种称为近似算法的算法。

算法性能评估的整个过程本质上是迭代进行的，如图1-11所示。