Mark Allen Weiss 著
陈越改编
人民邮电出版社出版
本翻译纯属个人爱好，没有任何商业性质，可供个人参考，但请勿传载！有问题请和jackzhhuang@hotmail.com联系。
翻译：黄中辉（哈尔滨理工大学计算机系）
第一章
介绍
在这一章里，我们讨论书中的论点和重点，并简要的复习编程概念。我们将 ：
·了解一个程序在相当大的输入下如何运行，这和适量输入下运行的情况同等重要。
·简要的复习递归算法。
1.1这本是什么样的书？
设想一下你有一组N个数字，并且想要确定第k个为最大值。这就是我们所知道的选择性问题。曾经选修过一门或者两门编程课程的学生可以没有任何困难的写出一个程序来解决这个问题。有一些很显然的方法。
一个解决方法是这N个数字输入到一个数组当中，使用诸如冒泡排序法给这组数组按降序排列，然后返回在第k位置的元素。
还有一个某种程度上更好的解决方法是将头k个元素输入到数组中，然后给它们排序（按降序排列），接下来，每一个剩下的元素被一个接一个的输入到数组中，每当一个新元素在输入的时候，如果它小于在数组中的第k个元素，那么它将被忽略掉。否则，将它放入到数组中的正确位置，并弹出一个元素。当这个算法结束时，处于第k位置的元素被返回作为答案。
两个算法都比较容易写出来，并且你被鼓励这么做。然而，一个最自然的问题是哪一个算法比较好？更重要的是两个算法是否足够好？一个模拟实验使用了有1亿个元素的随机文件，并使k=500，000，这个实验告诉我们：这两个算法没有一个可以在合理的时间内完成计算；没一个算法都需要计算机好几天的运算（虽然最后的结果正确）。一个替代算法将在第6章讨论。那里给出了一个约一秒钟计算完毕的解决方法。因此，虽然我们设计出了可行算法，但是它们未必可以看作是好算法，因为它们不能在输入数据量极大的情况下完全地合理执行，只有三分之一的算法可以在合理的总时间内处理问题。
第二个问题是解决一个流行字谜。输入是由一个二维字母数组和一个单词表组成。目的是在二维字母数组（既字谜）中找出单词表里面的单词。单词也许是水平方向的，垂直方向的，对角方向的任一方向。图1.1作为一个例子字谜，它包含了这些单词this，two，fat，that。单词this始于1行，1列，记作（1，1），然后延伸到（1，4）；two从（1，1）到（3，1）；fat从（4，1）到（2，3）；而that从（4，4）到（1，1）。
（未完待续）
