算法详解（卷1）——算法基础 - (EPUB全文下载)

文件大小：0.29 mb。
文件格式：epub 格式。
书籍内容：

算法详解（卷1）——算法基础
第1章 绪论
第2章 渐进性表示法
第3章 分治算法
第4章 主方法
第5章 快速排序（QuickSort）
第6章 线性时间级的选择
附录A 快速回顾数学归纳法
附录B 快速回顾离散概率
第1章 　绪论
本章的目标是激发读者学习算法的兴趣。我们首先介绍算法的基本概念以及它的重要性。接着，我们通过两个整数相乘的问题来说明精妙的算法是怎样改进那些简单或粗糙的解决方案的。然后，我们详细讨论了归并排序算法。之所以选择这个算法是出于下面这些理由：首先，它是一种非常实用并且非常有名的算法，是读者应该掌握的；其次，它是一种非常合适的“热身”算法，可以为以后学习更复杂的算法打下良好的基础；最后，它是分治算法设计范式的权威引导教程。在本章的最后，我们将描述一些算法分析的指导原则。在本书中，我们将使用这些原则对本书所介绍的算法进行分析。
1.1　为什么要学习算法
我们首先要阐明本书的价值，帮助读者激发学习算法的热情。那么，什么是算法呢？它是一组具有良好定义的规则（或者说是一种配方），可以有效地解决一些计算方面的问题。我们可能要处理一大串数字，需要对它们进行重新整理，使它们按顺序排列；我们可能需要在地图上计算从某个起点到某个目标地点的最短路径；我们可能需要在某个最后期限之前完成一些任务，并且需要知道应该按照什么样的顺序完成这些任务，使它们都能在各自的最后期限之前完成。
我们为什么要学习算法呢？
算法对计算机科学的所有分支都非常重要。在绝大多数的计算机科学分支领域中，要想完成任何实质性的工作，理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。例如，在斯坦福大学，每个级别（学士、硕士和博士）的计算机科学系都需要学习算法课。下面仅仅是算法应用的一些例子。
（1）通信网络中的路由协议需要使用经典的最短路径算法。
（2）公钥加密依赖于高效的数论算法。
（3）计算机图像学需要用到几何算法所提供的计算基元（computational primitive）功能。
（4）数据库的索引依赖于平衡搜索树这种数据结构。
（5）计算机生物学使用动态编程算法对基因的相似度进行测量。
类似的例子还有很多。
算法是技术革新的推动力。算法在现代的技术革新中扮演了一个关键的角色。最显而易见的一个例子是搜索引擎使用一系列的算法高效地计算与特定搜索项相关联的各个Web页面的出现频率。
这种算法最有名的例子是Google当前所使用的网页排名（PageRank）算法。事实上，在美国白宫2010年12月的一个报告中，总统的科学技术顾问作了如下的描述：
“每个人都知道摩尔定律，它是Intel的共同创立者Gordon Moore于1965年所作的一个预测：集成电路中的半导体密度每过一到两年就会扩大一倍……在许多领域，由于算法的改进所获得的性能提升甚至远远超过由于处理器速度的急剧增加所带来的性能提升。”[1]
算法会对其他科学产生影射。虽说这个话题超出了本书的范围，但算法就像一面“镜子”一样，越来越多地用于对计算机科学技术之外的过程进行影射。例如，对量子计算的研究为量子力学提供了一种新的计算视角。经济市场中的价格波动也可以形象地看作一种算法过程。
甚至，技术革新本身也可以看作一种令人吃惊的有效搜索算法。
学习算法有益于思维。当我还是一名学生时，我最喜欢的课程始终是那些具有挑战性的课程。当我艰苦地征服这些课程时，我甚至能够感觉到自己的智商比刚开始学习这些课程时提高了几个点。我希望本书也能够为读者提供类似的体验。
算法很有趣！最后，我希望读者在读完本书后认为算法的设计和分析是件简单而愉快的事情。这并非易事，因为它需要把精确和创新这两个特征罕见地结合在一起。它常常会给我们带来挫折，但有时会让我们深深入迷。别忘了，当我们还是小孩子时，就已经开始学习算法了。
[1]　节选自2010年12月向总统和国会所提供的报告：Designing a Digital Future（第71页）。
1.2　整数乘法
1.2.1　问题和解决方案
小学三年级的时候，我们很可能就学习了两数相乘的计算方法，这是一种具有良好定义的规则，把输入（2 个数）转换为输出（它们的乘积）。在这里，我们要注意区分两个不同的概念：一个是对需要解决的问题的描述，另一个是对解决方案所使用方法（也就是问题的算法）的描述。在本书中，我们所采用的模式是首先介绍一个计算问题（输入及其目标输出），然后描述一个或多个解决该问题的算法。
1.2.2　整数乘法问题
在整数乘法问题中，它的输入是两个n位数字的整数，分别称为x和y。x和y的长度n可以是任意正整数，但我鼓励读者把n看作一个非常巨大的数，几千甚至更大[2]。（例如，在有些加密应用程序中，可能需要将两个非常巨大的数相乘。）整数乘法问题的目标输出就是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相乘，并在必要时产生“进位”[3]。在计算下一个部分乘积（5678×3 = 17 034）时，我们执行相同的操作，并把结果左移一位，相当于在末尾添加一个“0”。对于剩下的两个部分乘积，也是执行相同的操作。最后一个步骤就是把所有的4个部分乘积相加。
图1.1　整数相乘的小学生算法
回想小学三年级的时候，我们接 ............

以上为书籍内容预览，如需阅读全文内容请下载EPUB源文件，祝您阅读愉快。