|
算法是什么？可能大多数读者都不能准确地给算法下一个定义。其实在日常生活中，我们已经在无意中接触过算法，通过本文，让我们更加深入地领略算法的奥妙！ 我们首先介绍算法的基本概念以及它的重要性。接着，我们通过两个整数相乘的问题来说明精妙的算法是怎样改进那些简单或粗糙的解决方案的。然后，我们详细讨论了归并排序算法。之所以选择这个算法是出于下面这些理由：首先，它是一种非常实用并且非常有名的算法，是读者应该掌握的；其次，它是一种非常合适的“热身”算法，可以为以后学习更复杂的算法打下良好的基础；最后，它是分治算法设计范式的权威引导教程。在本文的最后，我们将描述并使用算法分析的指导原则对本文所介绍的算法进行分析。 为什么要学习算法 我们首先要阐明本文的价值，帮助读者激发学习算法的热情。那么，什么是算法呢？它是一组具有良好定义的规则（或者说是一种配方），可以有效地解决一些计算方面的问题。我们可能要处理一大串数字，需要对它们进行重新整理，使它们按顺序排列；我们可能需要在地图上计算从某个起点到某个目标地点的最短路径；我们可能需要在某个最后期限之前完成一些任务，并且需要知道应该按照什么样的顺序完成这些任务，使它们都能在各自的最后期限之前完成。 我们为什么要学习算法呢？ 算法对计算机科学的所有分支都非常重要。在绝大多数的计算机科学分支领域中，要想完成任何实质性的工作，理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。例如，在斯坦福大学，每个级别（学士、硕士和博士）的计算机科学系都需要学习算法课。下面仅仅是算法应用的一些例子。 （1）通信网络中的路由协议需要使用经典的最短路径算法。 （2）公钥加密依赖于高效的数论算法。 （3）计算机图像学需要用到几何算法所提供的计算基元（computational primitive）功能。 （4）数据库的索引依赖于平衡搜索树这种数据结构。 （5）计算机生物学使用动态编程算法对基因的相似度进行测量。 类似的例子还有很多。 算法是技术革新的推动力。算法在现代的技术革新中扮演了一个关键的角色。最显而易见的一个例子是搜索引擎使用一系列的算法高效地计算与特定搜索项相关联的各个Web页面的出现频率。 这种算法最有名的例子是Google当前所使用的网页排名（PageRank）算法。事实上，在美国白宫2010年12月的一个报告中，总统的科学技术顾问作了如下的描述： “每个人都知道摩尔定律，它是Intel的共同创立者Gordon Moore于1965年所作的一个预测：集成电路中的半导体密度每过一到两年就会扩大一倍……在许多领域，由于算法的改进所获得的性能提升甚至远远超过由于处理器速度的急剧增加所带来的性能提升。” 算法会对其他科学产生影射。虽说这个话题超出了本文的范围，但算法就像一面“镜子”一样，越来越多地用于对计算机科学技术之外的过程进行影射。例如，对量子计算的研究为量子力学提供了一种新的计算视角。经济市场中的价格波动也可以形象地看作一种算法过程。 甚至，技术革新本身也可以看作一种令人吃惊的有效搜索算法。 学习算法有益于思维。当我还是一名学生时，我最喜欢的课程始终是那些具有挑战性的课程。当我艰苦地征服这些课程时，我甚至能够感觉到自己的智商比刚开始学习这些课程时提高了几个点。我希望本文也能够为读者提供类似的体验。 算法很有趣！最后，我希望读者在读完本文后认为算法的设计和分析是件简单而愉快的事情。这并非易事，因为它需要把精确和创新这两个特征罕见地结合在一起。它常常会给我们带来挫折，但有时会让我们深深入迷。别忘了，当我们还是小孩子时，就已经开始学习算法了。 整数乘法 1.2.1 问题和解决方案 小学三年级的时候，我们很可能就学习了两数相乘的计算方法，这是一种具有良好定义的规则，把输入（2 个数）转换为输出（它们的乘积）。在这里，我们要注意区分两个不同的概念：一个是对需要解决的问题的描述，另一个是对解决方案所使用方法（也就是问题的算法）的描述。在本文中，我们所采用的模式是首先介绍一个计算问题（输入及其目标输出），然后描述一个或多个解决该问题的算法。 在整数乘法问题中，它的输入是两 1.2.2 整数乘法问题 个n位数字的整数，分别称为x和y。x和y的长度n可以是任意正整数，但我鼓励读者把n看作一个非常巨大的数，几千甚至更大。（例如，在有些加密应用程序中，可能需要将两个非常巨大的数相乘。）整数乘法问题的目标输出就是x ·y这个乘积。 问题：整数乘法 输入：两个n位数字的非负整数x和y。 输出：x和y的乘积。 1.2.3 小学算法 精确地定义了计算问题之后，我们描述一种解决该问题的算法，这种算法和我们在小学三年级时所学习的算法是一样的。我们通过测量它所执行的“基本操作”的数量来评估这种算法的性能。现在，我们可以把基本操作看作下列的操作之一： （1）两个个位数相加； （2）两个个位数相乘； （3）在一个数的之前或之后添加一个0。 为了加深记忆，我们讨论一个具体的例子，把x = 5678和y = 1234（因此n = 4）这两个整数相乘。详细过程如图1.1所示。这种算法首先计算第一个数与第二个数最后一位数字的“部分乘积”：5678×4 = 22 712。计算这个部分乘积的过程又可以细分为把第一个数的每位数字与4相乘，并在必要时产生“进位”。在计算下一个部分乘积（5678×3 = 17 034）时，我们执行相同的操作，并把结果左移一位，相当于在末尾添加一个“0”。对于剩下的两个部分乘积，也是执行相同的操作。最后一个步骤就是把所有的4个部分乘积相加。  图1.1 整数相乘的小学生算法 回想小学三年级的时候，我们接受了这种算法的正确性。也就是说，不管x和y是什么整数，只要所有的中间计算过程都是正确的，这种算法最终能够得出两个输入数x和y的正确乘积。 也就是说，我们绝不会得到错误的答案，并且它不会陷入无限循环。 1.2.4 操作数量的分析 小学老师很可能不会讨论实现整数相乘这个过程所需要的基本操作的数量。为了计算第一个部分乘积，我们把4依次与第1个数的5、6、7、8相乘，这样就产生了4个基本操作。由于进位的原因，我们还需要执行一些加法操作。 一般而言，计算一个部分乘积涉及n个乘法（每位数字1个）以及最多n个加法（每位数字最多1个），总共最多是2n个基本操作。第一个部分乘积和其他几个部分乘积相比并没有任何特殊之处，每个部分乘积都是最多需要2n个基本操作。由于一共有n个部分乘积（第2个整数的每位数字各产生1个部分乘积），因此计算所有的部分乘积最多需要n · 2n = 2n2个基本操作。我们还需要把所有的部分乘积相加得到最终的答案，但这个过程仍然需要相当数量的基本操作（最多可达2n2）。该算法的基本操作的数量总结如下： 基本操作的数量 ≤ 常数（此例中为2）· n2 可以想象，当输入数的位数越来越多时，这种算法所执行的基本操作的数量也会急剧增加。如果把输入数的位数增加一倍，需要执行的基本操作的数量是原来的4倍。如果输入的位数是原来的4倍，那么基本操作的数量就是原来的16倍，以此类推。 1.2.5 还能做得更好吗 由于读者所接受的小学教育略有差异，有些读者可能会觉得上面这种方法是唯一可行的，还有些读者认为它至少是两数相乘最合适的方法之一。如果想成为一名严肃的算法设计师，那你必须要摆脱这种认为旧有方法理所当然的顺从思维。 Aho、Hopcroft和Ullman的经典算法名著在讨论了一些算法设计范式之后，对于这个问题提出了自己的见解： “或许，成为优秀算法设计师的最重要原则就是拒绝满足。” 或者如我所归纳的，每一名算法设计师都应该坚守下面这个信条： 我还能做得更好吗？ 当我们面对一个计算问题的简单解决方案时，这个问题就显得格外合适。在小学三年级时，老师不可能要求我们对这种简单的整数相乘算法进行改进。但是到了现在这个时候，无疑是提出这个问题的良好时机。 Karatsuba乘法 算法设计的空间之丰富达到了令人吃惊的程度，除了小学三年级所学习的方法之外，肯定还有其他有趣的方法可以实现两个整数的乘法。本节描述了一种名为Karatsuba乘法的方法。 1.3.1 一个具体的例子 为了让读者更方便了解Karatsuba乘法，我们还是沿用前面的x = 5678和y = 1234这个例子。我们将执行一系列与之前的小学算法截然不同的步骤，最终也生成x · y这个乘积。这些步骤序列可能会让读者觉得非常神秘，就像魔术师突然从自己的帽子里拽出一只兔子一样。在本节的后面，我们将介绍什么是Karatsuba乘法，并解释它的工作原理。现在，我们需要领悟的一个关键要点就是我们可以通过许多令人眼花缭乱的方法来解决诸如整数乘法这样的计算问题。 首先，我们把x的前半部分和后面部分划分开来，并分别为它们命名为a和b（因此a = 56，b = 78）。 类似，c和d分别表示12和34（图1.2）。  图1.2 把一个4位整数看成是一对两位整数 接着，我们执行一系列的操作，它们只涉及两位数a、b、c和d，并最终用一种神奇的方法把它们组合在一起，产生x和y的乘积。 步骤1：计算a · c = 56 × 12，其结果为672（欢迎读者验算）。 步骤2：计算b · d = 78 × 34 = 2652。 接下来的两个步骤显得更加神秘： 步骤3：计算( a + b) · ( c + d ) = 134 × 46 = 6164。 步骤4：步骤3的结果减去前两个步骤的结果6164 – 672 – 2562 = 2840。 最后，我们把步骤1、2、4的结果相加，不过在此之前先在步骤1的结果后面加上4个0，在步骤4的结果后面加上2个0。 步骤5：计算104×672 + 102 × 2840 + 2652 = 6 720 000 + 284 000 + 2652 = 7 006 652。 这个结果与第1.2节的小学算法所产生的结果完全相同！ 读者肯定不明白这中间到底发生了什么。我希望读者既对此感到困惑，又为此入迷，并且非常愉快地发现除了小学所学习的整数相乘算法之外，还存在其他完全不同的算法。一旦意识到算法空间之广阔，我们就会萌生这样的想法：我们能不能比小学算法做得更好？上面所描述的这种算法是不是更加优秀？ 1.3.2 一种递归算法 在详细分析Karatsuba乘法之前，我们先探索一种更简单的处理整数乘法的递归方法 。整数乘法的递归算法大致可以理解为调用更少位数的整数乘法（例如在上面的例子中，先执行12、34、56、78这些整数的乘法）。 一般而言，位数为偶数n的数x可以表示为2个n/2位的数，即它的前半部分a和后半部分b： x = 10n/2 · a + b 类似，我们也可以得到下面的结果： y = 10n/2 · c + d 为了计算x和y的乘积，我们使用上面这两个表达式并把它们相乘： x · y = (10n/2 · a + b) · (10n/2 · c + d) = 10n · ( a · c) + 10n/2 · ( a · d + b · c ) + b · d （1.1） 注意，表达式（1.1）中的所有乘法要么是在一对n/2位的整数之间进行的，要么涉及10的乘方。 表达式（1.1）提示用一种递归方法进行两个整数的相乘。为了计算 x · y这个乘积，我们对表达式（1.1）进行计算。4个相关的乘积（a · c、a · d、b · c和b · d）所涉及的位数都少于n，因此我们可以用递归的方式计算它们。当这4个递归调用带着各自的答案返回时，我们就可以很简单地计算表达式（1.1）的值了：在a · c后面加上n个0；把a · d和b · c相加（使用小学加法），并在得出的结果后面加上n/2个0，并最终把这两个表达式与b · d相加。我们用下面的伪码对这种名为RecIntMult的算法进行总结。 RecIntMult 输入：两个n位正整数x和y。 输出：x和y的乘积。 先决条件：n是2的整数次方。  RecIntMult算法和小学算法相比是更快还是更慢呢？现在读者对这个问题应该不会有直观的感觉，我们将在第4章讨论这个问题的答案。 1.3.3 Karatsuba乘法 Karatsuba乘法是RecIntMult算法的一种优化版本。我们仍然从根据a、b、c、d进行了扩展的x·y表达式（1.1）开始。RecIntMult算法使用了4个递归调用，分别用于表达式（1.1）中的每个n/2位数之间的乘积。我们事实上并不真正关心a · d或b · c，只是关注它们的和a · d + b · c。由于我们真正关心的只有3个值：a · c、a · d + b · c和b · d，那么是不是只用3个递归调用就可以了呢？ 为了观察这种想法是否可行，我们首先像前面一样以递归的方式调用a · c和b · d。 步骤1：用递归的方式计算a · c。 步骤2：用递归的方式计算b · d。 我们不再递归地计算a · d 或b · c，而是递归地计算a + b和c + d的乘积。 步骤3：计算a + b和c + d（使用小学加法），并以递归的方式计算(a + b)·(c + d)。 Karatsuba乘法所使用的关键技巧来源于19世纪早期的著名数学家Carl Friedrich Gauss，这是他在思考复数乘法时所想到的方法。从步骤3的结果中减去前两个步骤的结果所得到的值正是我们所需要的，也就是表达式（1.1）中a · d + b · c的中间系数：  步骤4：从步骤3的结果中减去前两个步骤的结果，获得a · d + b · c的值。 最后一个步骤就是计算表达式（1.1），其方法与RecIntMult算法相同。 步骤5：在步骤1的结果后面加上n个0，在步骤4的结果后面加上n/2个0，然后将它们与步骤2的结果相加，以计算表达式（1.1）。  Karatsuba乘法只进行了3个递归调用！节省1个递归调用应该能够节省整体运行时间，但能够节省多少呢？Karatsuba算法是不是比小学乘法更快？答案并不显而易见，不过我们将在第4章引入一个方便的应用工具，用于对这类分治算法的运行时间进行分析。 MergeSort算法 在本节中，我们第一次对一个具有相当深度的算法的运行时间进行分析，这个算法就是著名的MergeSort（归并排序）算法。 1.4.1 推动力 MergeSort是一种相对古老的算法，早在1945年就由约翰·冯·诺依曼提出并广为人知。我们为什么要在现代的算法课程中讨论这样的古老例子呢？ 姜还是老的辣。尽管已经70岁“高龄”，但MergeSort仍然是一种可供选择的排序算法。它在实践中被一直沿用，仍然是许多程序库中的标准排序算法之一。 经典的分治算法。分治算法设计范式是一种通用的解决问题的方法，在许多不同的领域有着大量的应用。它的基本思路就是把原始问题分解为多个更小的子问题，并以递归的方式解决子问题，最终通过组合子问题的解决方案得到原始问题的答案。MergeSort可以作为一个良好的起点，帮助我们理解分治算法范式以及它的优点，包括它所面临的分析挑战。 校准预备条件。本节对MergeSort的讨论可以让读者明白自己当前的技术水平是否适合阅读本文。我假设读者具有一定的编程和数学背景（具有一定实践经验），能够把MergeSort的高级思路转换为自己所喜欢的编程语言的工作程序，并且能够看懂我们对算法所进行的运行时间分析。如果读者能够适应本节和下一节的内容，那么对于本文的剩余部分也不会有什么问题。 推动算法分析的指导原则。本节对MergeSort运行时间的分析展示了一些更加基本的指导原则，例如探求每个特定长度的输入的运行时间上界以及算法的运行时间增长率的重要性（作为输入长度的函数）。 为主方法热身。我们将使用“递归树方法”对MergeSort进行分析，这是一种对递归算法所执行的操作进行累计的方法。第4章将集合这些思路生成一个“主方法”。主方法是一种功能强大且容易使用的工具，用于界定许多不同的分治算法的运行时间，包括第1.3节所讨论的RecIntMult和Karatsuba算法。 1.4.2 排序 读者很可能对排序问题以及一些解决排序问题的算法已经有所了解，我们姑且把它们放在一起。 问题：排序 输入：一个包含n个数的数组，以任意顺序排列。 输出：包含与输入相同元素的数组，但它们已经按照从小到大的顺序排列。 例如，假设输入数组是：  目标输出数组是：  在上面这个例子中，输入数组中的8个数是各不相同的。即使数组中出现了重复的数，排序也不会变得更困难，甚至变得更简单。但是，为了尽可能地简单，我们假设输入数组中的数总是不同的。我积极鼓励读者对我们所讨论的排序算法进行修改（如果可以修改），使之能够处理重复的值。 如果读者并不关注运行时间的优化，那么要想实现一种正确的排序算法并不困难。也许最简单的方法就是首先对输入数组进行扫描，找到最小的元素并把它复制到输出数组的第1个元素，接着扫描并复制次小的元素，接下来依次类推。这种算法称为SelectionSort（选择排序）。读者可能听说过InsertionSort（插入排序），这是同一个思路的一种更灵巧的实现方法，它把输入数组中的每个元素依次插入到有序的输出数组中的适当位置。读者可能还听说过BubbleSort（冒泡排序），它需要对一对对相邻的无序元素进行比较，并执行反复的交换，直到整个数组实现了排序。所有这些算法所需要的运行时间都是平方级的，意味着对长度为n的数组所执行的操作数量级是n2，即输入长度的平方。我们能不能做得更好？通过分治算法的范式，我们可以发现MergeSort算法较之这些简单的排序算法能够大幅度地提高性能。 1.4.3 一个例子 理解MergeSort最容易的方法就是通过一个具体的例子（图1.3）。我们将使用1.4.2节的输入数组。 作为一种递归的分治算法，MergeSort以更小的输入数组调用自身。把一个排序问题分解为多个更小的排序问题的最简单方法就是把输入数组对半分开，并分别以递归的方式对数组的前半部分和后半部分进行排序。例如，在图1.3中，输入数组的前半部分和后半部分分别是{5, 4, 1, 8}和{7, 2, 6, 3}。通过神奇的递归（如果读者喜欢，也可以称为归纳），第一个递归调用对前半部分进行正确的排序，返回数组{1, 4, 5, 8}。第二个递归调用则返回数组{2, 3, 6, 7}。  图1.3 通过一个具体例子领会MergeSort 最后的“归并”步骤把这两个已经排序的长度为4的数组组合为一个已经排序的包含8个数的数组。下面描述了这个步骤的细节，其思路是通过索引遍历每个已经排序的子数组，并按照从左到右的有序方式生成输出数组。 1.4.4 伪码 图1.3大致相当于下面的伪码。对于通用的问题，它有两个递归调用和一个归并步骤。和往常一样，我们的描述并不需要逐行转换为工作代码（尽管已经相当接近）。  这段伪码省略了一些内容，这些内容值得予以说明。作为一种递归算法，它必须有一个或多个基本条件，如果不再有进一步的递归，就直接返回答案。因此，如果输入数组A只包含0个或1个元素，MergeSort就返回该数组（它显然已经排序）。这段伪码并没有详细说明当n是奇数时，“前半部分”和“后半部分”是怎么划分的，但那种显而易见的理解（其中一半比另一半多一个元素）是可行的。最后，这段伪码忽略了怎么把两个子数组实际传递给它们各自的递归调用的实现细节。这些细节取决于编程语言。高级伪码的要点就是忽略这类细节，把注意力集中在超越任何特定编程语言的概念上。 1.4.5 Merge子程序 我们应该怎样实现归并步骤呢？此时，两个递归调用已经完成了它们的工作，我们拥有了两个已经排序的长度为n/2的子数组C和D。我们的思路是按顺序遍历这两个已经排序的子数组，并按照从左到右的方式有序地生成输出数组。  我们根据索引k遍历输出数组，根据索引i和j遍历已经排序的子数组。这3个数组都是从左向右进行遍历的。第3行的for循环实现向输出数组的传递。在第一次迭代中，这个子程序确认C或D中的最小元素，并把它复制到输出数组B的第一个位置。最小元素要么在C（此时为C[1]，因为C是经过排序的），要么在D（此时为D[1]，因为D是经过排序的）。把对应索引（i或j）的值加1就有效地略过了刚刚已经被复制的元素。再次重复这个过程，寻找C或D中剩余的最小元素（全体中的第二小元素）。一般而言，尚未被复制到B的最小元素是C[i]或D[j ]。这个子程序检查哪个元素更小，并进行相应的处理。由于每次迭代都是复制C或D中所剩下的最小的那个元素，因此输出数组确实是按有序的方式生成的。 和往常一样，我们的伪码有意写得比较粗略，这是为了强调整片森林而不是具体的树木。完整的实现应该要追踪C或D是否已经遍历到了数组的末尾，此时就把另一个数组的所有剩余元素都复制到数组B的最后部分（按顺序）。现在，就是读者自行实现MergeSort算法的好时机。 本文要点
《算法详解（卷1）——算法基础》 Tim Roughgarden 著 算法详解系列图书共有4卷，本书是第一卷——基础算法。本书共有6章，主要介绍了4个主题，它们分别是渐进性分析和大O表示法、分冶算法和主方法、随机化算法以及排序和选择。附录A和附录B简单介绍了数据归纳法和离散概率的相关知识。本书的每一章均有小测验、章末习题和编程题，这为读者的自我检查以及进一步学习提供了较多的便利。 |
|
|
