1.3 软件和算法理论中的复杂性
软件中某一小部分可能与软件开发过程同样复杂。软件工程中有许多用来度量软件复杂性的指标。
首先，我们来看看算法复杂度，它与不同算法的资源需求有关。利用算法复杂度指标，您可以比较针对同一问题的不同算法。例如，假设您已经实现了一个带有分数评级系统的游戏应用。您希望分数最高的玩家出现在列表顶部，分数最低的玩家出现在底部。换句话说，您需要对列表进行排序。存在数千种对列表进行排序的算法，对1,000,000名球员进行排序在计算上比对100名球员进行排序的要求更高。有些算法随着列表输入规模的增长而表现得更好，有些算法的表现却更差。当应用程序为几百个用户服务时，选择哪种算法其实并不重要，但随着用户群的增长，列表运行时的复杂度会超线性增长。很快，终端用户将不得不等待越来越久的列表排序时间。他们会开始抱怨，而您则需要更好的算法。
图1-2举例说明了两种示意性算法的复杂度。横轴显示了待排序列表的大小。纵轴显示算法的运行时间（以时间为单位）。算法1比算法2慢得多。事实上，要排序的列表元素越多，算法1的低效率问题就越明显。使用算法1，玩家越多，游戏应用程序将变得越慢。
图1-2 两个排序算法的复杂度
让我们看看这在真正的Python排序例程中是否成立。图1-3比较了3种流行的排序算法：冒泡排序、快速排序和蒂姆排序（Timsort[ 2002年由Tim Peters使用Python语言实现。——译者注]）。冒泡排序算法的复杂度最高，快速排序算法和蒂姆排序算法具有相同的算法渐进复杂度，但是蒂姆排序算法仍然快得多——这就是它被用作Python默认排序程序的原因。冒泡排序算法的运行时间随着列表大小的增加而爆炸式增加。
在图1-4中，我们重复这个实验，但只针对快速排序算法和蒂姆排序算法。同样，二者的算法复杂度也有巨大差异：蒂姆排序算法的处理规模适应性更好，对于不断增长的列表大小来说速度更快。现在您明白为什么Python内置的排序算法已经很久没变了吧！
图1-3 冒泡排序算法、快速排序算法和蒂姆排序算法的算法复杂度
图1-4 快速排序算法与蒂姆排序算法的算法复杂度
如果您想重现这个实验，可以参见代码清单1-1。建议您选择一个较小的n值，因为这段代码在我的计算机上运行了很长时间才结束。
代码清单1-1 度量3种流行排序算法的运行时间
算法复杂度早已被研究透彻了。在我看来，从研究中产生的改进算法是人类最宝贵的技术资产之一。它使我们能够以更少的资源去解决同样的问题。我们真正站在了巨人的肩膀上。
除了算法复杂度，我们还可以用循路复杂度（cyclomatic complexity）来衡量代码的复杂度。这个指标是由托马斯·麦凯布（Thomas McCabe）在1976年开发的，它描述了通过代码的线性无关（linearly independent）路径的数量，或至少有一条边不在其他路径上的路径的数量。例如，带有if语句的代码会导致两条独立路径通过您的代码，所以其循路复杂度会比没有分支的普通代码高。图1-5显示了两个处理用户输入并作出相应反应的Python程序的循路复杂度。第一个程序只包含一个条件分支，这可以说是一个岔路口。任何一个分支都可以被使用，但不能同时使用。因此，循路复杂度为2，因为有两条线性无关的路径。第二个程序包含两个条件分支，总共有3条线性无关的路径，循路复杂度为3。每一个额外的if语句都会增加循路复杂度。
图1-5 两个Python程序的循路复杂度
循路复杂度是可靠的代用指标，用于衡量认知复杂度，即理解一个特定代码库的难度。然而，循路复杂度没有覆盖一些情况，例如与普通for循环相比，多个嵌套for循环带来的认知复杂度。NPath之类其他度量标准在循路复杂度的基础上有所改进。总而言之，代码复杂度不仅是算法理论的重要课题，而且与实现代码时的全部实际问题有关，也与编写易于理解、可读和强固的代码有关。几十年来，算法理论和编程复杂度都得到了深入的研究。这些努力的主要目标之一是减少计算和非计算的复杂度，减轻其对人类和机器生产力及资源利用的有害影响。
