解释算法的实现逻辑就像讲故事一样。算法会在普通的解决方案中引入新颖的思路或进行某种创新。在本章中，我们将讨论一个简单问题的几个解决方案，解释影响算法性能的一些因素。在这个过程中，我将介绍一些用于分析算法性能的技巧。这些技巧与算法的实现无关，尽管我在讨论中总是会提供实际实现的实验证据。

图标2算法是一种逐步解决问题的方法，可实现为计算机程序的形式，能够在可预测的时间内返回正确的结果。算法的研究既要关注正确性（它对于所有的输入是否都能发挥作用？），也要关注性能（它是解决这个问题的最有效方法吗？）。

下面我们详细观察一个算法的例子，看看它实际上是怎么处理问题的。如果我们想在一个无序列表中查找最大值，应该怎么办？图1-1中的每个Python列表都是一个问题实例（problem instance），也就是算法（用圆柱体显示）所处理的输入。正确答案出现在算法的右边。这个算法是如何实现的？它在不同的问题实例上是如何执行的？我们能不能预测在一个包含1,000,000个值的列表中查找最大值所需要的时间？

图1-1　一个算法所处理的3个不同的问题实例

算法不仅仅是一种问题解决方法。实现算法的程序还需要在可预测的时间内完成任务。Python的内置函数max()已经解决了上面这个问题。现在，对于包含随机数据的问题实例，预测算法的性能可能比较困难，因此找到精心构建的问题实例是极有价值的。

表1-1显示了在两种类型的规模为N的问题实例上执行max()需要的时间。一种是以升序排列的整数列表，另一种是以降序排列的整数列表。由于读者所使用的计算机系统的配置不同，得到的执行结果可能与表中的不同，但仍然符合下面这两个结论：

● 当N足够大时，在递增的值上执行max()需要的时间总是要多于递减的值需要的时间；

● 当后面每一行的N值都为前一行的10倍时，max()的对应时间尽管稍有偏差，但大致也是原来的10倍，这也与我们的生活经验相符。

上述问题实例中，max()返回最大值，输入并没有被修改。在有些情况下，算法会直接更新问题实例而不是计算一个新值，我们将在第5章学习的对一个值列表进行排序的算法就是这样的。在本书中，N表示问题实例的规模。

表1-1　在两种类型的规模为N的问题实例上执行max()需要的时间　　单位：ms

关于执行算法所需要的时间：

● 我们无法事先预测T(100000)的值（即算法处理一个规模为100,000的问题实例所需要的时间）是多少，因为计算平台可能并不相同，实现算法所使用的编程语言也可能不同；

● 但是，一旦通过实验确定了T(10000)所需要的时间，就可以对T(100000)，也就是解决一个10倍规模的问题实例所需要的时间进行预测，尽管这种预测不可避免地和准确时间有所出入。

在设计算法时，基本的挑战是保证它的正确性，使之适用于所有的输入。我将在第2章使用更多的篇幅解释如何对解决同一个问题的不同算法的行为进行分析和比较。算法分析这个领域与现实生活中发生的有趣的、重要的问题的研究息息相关。由于算法所蕴含的数学知识理解起来具有一定的难度，我将提供一些特定的例子，实现抽象的概念与现实世界的问题的关联。

计算算法效率的标准方法是对它所需要的计算操作进行计数，但这是极难做到的！计算机中执行机器指令的中央处理器（CPU），负责执行数学计算（例如加法和乘法）、CPU寄存器的赋值、两个值的比较等任务。有些现代的编程语言（例如C或C++）被编译为机器指令，还有一些编程语言（例如Python或Java）被编译为中间字节码表示形式。Python解释器（本身是C语言程序）执行字节码，而像min()和max()这样的内置函数是用C语言实现的，最终会被编译为机器指令而执行。

强大的数组

数组是指在一块连续的内存中存储N个值的集合。它是程序员存储多个值时所使用的最“古老”也最可靠的数据结构之一。图1-2表示一个包含8个整数的数组。

图1-2　包含8个整数的数组

数组A有8个值，可根据位置进行索引。例如，A[0]=31、A[7]=5。A中的值可以是任何类型，例如字符串或者更为复杂的对象。

下面是与数组有关的一些重要知识：

● 第1个值A[0]的索引位置是0，最后一个值的索引位置是A[N–1]，其中N表示数组的长度；

● 每个数组都具有固定的长度，Python和Java允许程序员在运行时确定数组的长度，但C语言不允许；

● 可以通过索引位置i读取或更新数组中的一个单独值A[i]，i是一个0～N − 1范围内的整数；

● 数组无法直接被扩展（或收缩），但是我们可以分配一个目标大小的新数组，并把旧数组中应该保留的值复制到这个新数组。

数组非常简单，它在组织数据时具有极广的用途和极高的效率。在Python中，list（列表）对象可以看成数组，它的功能更加强大，因为它能够随时扩展和收缩。

要对一个算法所执行的机器指令的总数进行统计几乎是不可能的，何况现代的CPU每秒可以执行数十亿条指令！我将改而对每个算法所调用的关键操作的数量进行统计，这可能是“数组中两个值的比较次数”或“一个函数的调用次数”。在max()函数的讨论中，关键操作是“小于操作（<）被调用了多少次”。我将在第2章中解释这个计数原则。

现在，是时候揭开max()算法的面纱了。

上一章目录下一章