算法基础（第5版）[试读]
1.1 算法
本书讨论用计算机解决问题的方法。这里所说的“方法”并不是指一种程序设计风格或者一种程序设计语言，而是用于解决问题的方法或方法学。例如，假设Barney Beagle希望在电话簿中找到名字“Collie, Colleen”。一种方法是从第一个名字开始，依次查看每个名字，直到找出“Collie, Colleen”为止。但是，没有人会这样来找一个名字。电话簿中的名字都是有序的，所以Barney会利用这一事实，将电话簿翻到他认为C字头名字所在的位置。如果他翻过了，可以往回翻一些。他不停地前后翻动，直到找出“Collie, Colleen”所在的页面。你可能看出来了，第二种方法就是一种经过修改的二分查找... 查看全部[ 1.1 算法 ]
1.2 开发高效算法的重要性
前面曾经提到，无论计算机变得多么快速，内存变得多么廉价，效率永远都是重要的考虑因素。接下来，我们通过对比同一问题的两种算法来说明其原因。 1.2.1 顺序查找与二分查找的对比 前面曾经提到，在电话簿中查找姓名的方法是一种经过修改的二分查找，它通常要远快于顺序查找。下面将对比这两种方法的算法，以说明二分查找法要快多少。 我们已经编写了完成顺序查找的算法，即算法1.1。在一个非递减顺序数组中进行二分查找的算法类似于用大拇指前后翻动电话簿。也就是说，假定正在查找x，算法首先将x与数组的中间项进行对比。如果相等，则算法完成。如果x小于中间项，则x必然在数组的前半部分（如果存在的话），... 查看全部[ 1.2 开发高效算法的重要性 ]
1.3 算法分析
为了判断一种算法在解决某种问题时的效率如何，需要分析算法。在前一节比较算法时，引入了算法的效率分析。但这些分析过程相当随意，不够正式。我们现在讨论算法分析中使用的术语以及标准的分析方法。在本书后续部分将遵循这些标准。 1.3.1 复杂度分析 在分析一种算法的时间效率时，并没有计算出实际CPU周期数，因为这一数值取决于运行算法的具体计算机。此外，我们甚至不希望计算所执行的指令数，因为指令数取决于用于实现算法的程序设计语言，以及程序员编写程序的方式。我们希望有一种量度，不受计算机、程序设计语言、程序员、算法的所有复杂细节（比如循环索引的递增、指针设定等）的影响。通过对比两种算法在不同n... 查看全部[ 1.3 算法分析 ]
1.4 阶
前面刚刚阐明，对于时间复杂度分别为n和n²的两种算法，无论两种算法需要多长时间来处理基本运算，当n值足够大时，第一种算法的效率总是高于第二种。现在假定同一问题有两种算法，而且第一种算法的所有情况时间复杂度为100n，第二种算法为0.01n²。根据上面刚刚给出的论述，可以证明，第一种算法的效率最终会高于第二种算法。例如，如果两种算法处理基本运算需要的时间相同，而且开销时间也大致相同，则当 0.01n² > 100n 时，第一种算法更为高效。 两边同除以0.01n，得： n > 10 000 如果第一种算法处理基本运算的时间长于第二种算法，第一种算法最终还是会变得... 查看全部[ 1.4 阶 ]
1.5 本书概要
我们现在已经为复杂算法的设计与分析做好了准备。本书大部分内容都是根据技术而非应用领域进行组织的。前面已经提到，这种组织方式的目的是为了建立一个方法库，在遇到新问题时，可从其中选择可能的解决方法。第2章讨论“分而治之”方法。第3章介绍动态规划，第4章讨论“贪婪方法”。第5章介绍回溯技术。第6章讨论一种与回溯有关的方法，名为“分支定界”。第7章和第8章从算法的设计与分析转为分析问题本身。这种分析称为计算复杂度分析，主要计算对于一个给定问题，其所有算法的时间复杂度下限。第7章分析排序问题，第8章分析查找问题。第9章专门讨论一种特殊类别的问题。对于这类问题，人们还从来没有开发出一种算法，使其时间复杂度... 查看全部[ 1.5 本书概要 ]
1.6 习题
1.1节 1. 编写一个算法，在一个包含n个数字的列表（数组）中找出最大数。 2. 编写一个算法，在一个包含n个数字的列表中找出最小数。 3. 有一个包含n个元素的集合，其元素存储在一个列表中。编写一个算法，以该列表为输入，输出该集合的所有三元素子集。 4. 编写一个“插入排序”算法（插入排序在7.2节讨论），使用二分查找法找出下一个插入位置。 5. 编写一个算法，计算两个整数的最大公约数。 6. 编写一个算法，在一个包含n个数字的列表中找出最大数和最小数。尝试找出一种方法，对数组项进行的比较次数不超过1.5n次。 7. 编写一个算法，确定一个准完全二... 查看全部[ 1.6 习题 ]
书名： 算法基础（第5版）
作者： [美] Richard E·Neapolitan
出版社： 人民邮电出版社
原作名： Foundations of Algorithms
译者： 贾洪峰
出版年： 2016-3
页数： 408
定价： 99.00元
装帧： 平装
丛书： 图灵计算机科学丛书
ISBN： 9787115416575