如何看待算法

• 摘自：《HOW TO THINK ABOUT ALGORITHMS
• 作者：JEFF EDMONDS

There are many algorithm texts that provide lots of well-polished （擦 亮的, 优美的, 精练的 ） code and proofs of correctness. Instead, this one presents insights, notations, and analogies to help the novice（新手, 初学者） describe and think about algorithms like an expert. It is a bit like a carpenter（木匠） studying hammers instead of houses. Jeff Edmonds provides both the big picture and easy step-by-step methods for developing algorithms, while avoiding the common pitfalls. Paradigms such as loop invariants and recursion help to unify （ 统一, 使成一体）a huge range of algorithms into a few meta-algorithms .

Part of the goal is to teach students to think abstractly. Without getting bogged（陷入泥沼） down in formal proofs, the book fosters（养育; 培养; 抚育） deeper understanding so that how and why each algorithm works is transparent. These insights are presented in a slow and clear manner accessible to second- or third-year students of computer science, preparing them to find on their own innovative ways to solve problems.

目前很多算法教材都只是提供大量优美精练代码和对这些代码的正确性证明，然而，要学会建造房子得学会使用锤子而不是光研究现成房子的结构，所以光有这些代码对初学者进化为 算法设计者 是不够的，或者说很难帮助初学者顺利快速演化成 算法设计专家 。本书设法弥补这方面的不足。著者在书中使用了一些设计模式（Paradigms ），比如循环不变量和递归，把大量算法归类成少量的元算法（ meta-algorithms ）。(KEMIN: 这种做法有助于看清算法设计的本质而不至于掉进问题堆中找不着北）这样做也有助于训练读者的抽象思维能力。著者也试图绕开严格的形式证明而帮助读者深刻理解为什么算法的正确性是明显和理所当然的。著者通过使用一些详尽清晰和对二三年级的计算机科学的学生可理解的方式达到这个目的，为他们将来算法创新打下基础。

Abstraction is when you translate the equations, the rules, and the underlying essences of the problem not only into a language that can be communicated to your friend standing with you on a streetcar, but also into a form that can percolate（浸透; 渗出） down and dwell（居住; 踌躇） in your subconscious（下意识, 潜意识）. Because, remember, it is your subconscious that makes the miraculous（奇迹的; 不可思议的） leaps（跳跃, 急变） of inspiration, not your plodding（沉重缓慢的, 单调乏味的） perspiration（汗, 努力, 流汗） and not your cocky（骄傲的, 自大的） logic. And remember, unlike you, your subconscious does not understand Java code.

抽象思维能力表现为一种潜意识态度而不是简单对知识的运用。转换公式、规则和问题的本质为语言表达并与人交流只是知识的运用，是能力的浅层次获得；能力的深层次获得是浸透入我们的潜意识里[注1]。因为，我们思维时候，灵感的跳跃是来自潜意识的驱使，不是机械式的努力和强人逻辑所能得到的。还有，和你 （显意识）不一样，你的潜意识是不明白JAVA代码的。

注1：合格的算法设计者或者抽象思维能力的潜意识层获得有什么可操作的标准吗？

PREFACE

To the Educator and the Student

This book is designed to be used in a twelve-week, third-year algorithms course. The goal is to teach students to think abstractly about algorithms and about the key algorithmic techniques used to develop them.

本书编写有两个目的，第一，教育学生抽象地看待算法；第二，教育学生开发（设计）算法的关键技术。

Meta-Algorithms :

Students must learn so many algorithms that they are sometimes overwhelmed（受不起, 不敢当 ）. In order to facilitate their understanding, most textbooks cover the standard themes of iterative algorithms, recursion, greedy algorithms, and dynamic programming.Generally, however,when it comes to presenting the algorithms themselves and their proofs of correctness, the concepts are hidden within optimized code and slick（光滑的） proofs. One goal of this book is to present a uniform and clean way of thinking about algorithms. We do this by focusing on the structure and proof of correctness of iterative and recursive meta-algorithms, and within these the greedy and dynamic programming meta-algorithms. By learning these and their proofs of correctness, most actual algorithms can be easily understood. The challenge is that thinking about meta-algorithms requires a great deal of abstract thinking.

为了成为合格的算法设计者，学生得研究大量的算法例子，而这个数量往往超出了一般学生所能接受的程度。为了帮助同学们理解算法，一般的教材都会讲述标准的主题，如迭代算法、递归、贪心算法和动态规则等。但结果常常是只给出优化的代码和漂亮的证明，得到这些代码和证明背后的原理却没有讲。这些原理就本书的中心——元算法。掌握了元算法就通晓了大部分的算法例子，唯一的代价就是大量的抽象思维。

Abstract Thinking :

Students are very good at learning how to apply a concrete code to a concrete input instance. They tend, however, to find it difficult to think abstractly about the algorithms. I maintain that the more abstractions a person has from which to view the problem, the deeper his understanding of it will be, the more tools he will have at his disposal（安排, 配置, 支配 ）, and the better prepared he will be to design his own innovative ways to solve new problems. Hence, I present a number of different notations, analogies, and paradigms within which to develop and to think about algorithms.

学生一般都善于学习为具体问题实例套用具体算法代码，但却很难抽象地看待算法。我发现，如果一个人他越能抽象地看待要处理的问题，他就越能深刻地理解问题的本质，也越有更多的解决问题的工具，也越容易独自创新。为了训练出这样的抽象思维能力，我使用了一特别的教学方式：different notations, analogies, and paradigms。

Way of Thinking :

People who develop algorithms have various ways of thinking and intuition that tend not to get taught. The assumption, I suppose, is that these cannot be taught but must be figured out on one's own. This text attempts to teach students to think like a designer of algorithms.

人在设计算法时的思维方式和直觉是无法教的，必须由自己慢慢调整。本书设法引导同学们的思维向算法设计师方向调整。

Not a Reference Book :

My intention is not to teach a specific selection of algorithms for specific purposes. Hence, the book is not organized according to the application of the algorithms, but according to the techniques and abstractions used to develop them.

我的目的不是给一个特定的问题讲授一个特定的算法，所以本书不是根据算法的应用来组织的，而是根据算法设计的技术和抽象方法来组织的。

Dreaming :

I would like to emphasis the importance of thinking, even daydreaming, about the material. This can be done while going through your day –while swimming, showering, cooking, or lying in bed. Ask questions. Why is it done this way and not that way? Invent other algorithms for solving a problem. Then look for input instances for which your algorithm gives the wrong answer. Mathematics is not all linear thinking.

If the essence of the material, what the questions are really asking, is allowed to seep（渗出, 漏, 渗流 ） down into your subconscious then with time little thoughts will begin to percolate up. Pursue these ideas. Sometimes even flashes of inspiration appear.

我必须强调对材料的思考和联想的重要性。这种思考可以随时随地的进行。“为什么如此而不是那样呢？”。试着为问题开发新的算法，找出你的算法有可能错误处理的问题实例。记住，数学不能使用简单的线性思维。注意，如果我们问中了一个本质的问题，那么它就很可能进入我们的潜意识[注2]。因此对思想的追捕，即便是瞬间的灵思， 是非常重要的。

注2： Kemin says: a.如果我的猜测是对的话，学习的本质是让知识上升为态度，显意识进入潜意识，那么什么样的显意识知识才有助于逻辑进化，又需要多少这样的知识呢？

Kemin says: a.从心理一层看，一些东西能进入人的潜意识的前提是对心灵的莫大的触动；首先这个触动没法量化；第二，触动的根源又是什么呢？我们知道小时候留下的心灵创伤应该是当时生理或心理上非常惧怕的东西造成的。惧怕的原因是需要和不需要，需要是进入人的潜意识的动力源？！

Kemin says: a.其实不必夸大态度和潜意识的神秘性，它们应该也是基于我们可掌握可触摸的知识和显意识的。只是改变态度所要的知识量和知识种类确实还是未知。目前只知道知识量很大，知识种类应该是系统的。

Introduction From determining the cheapest way to make a hot dog to monitoring the workings of a factory, there are many complex computational problems to be solved. Before executable code can be produced, computer scientists need to be able to design the algorithms that lie behind the code, be able to understand and describe such algorithms abstractly, and be confident that they work correctly and efficiently. These are the goals of computer scientists.

计算机科学家的职责：计算机科学家的职责和能力在于，第一，抽象地描述解决计算问题（computational problems）的算法；第二，证明算法的正确性；第三，证明算法的有效性。

A Computational Problem:

A specification of a computational problem uses preconditions and postconditions to describe for each legal input instance that the computation might receive, what the required output or actions are. This may be a function mapping each input instance to the required output. It may be an optimization problem which requires a solution to be outputted that is “optimal” from among a huge set of possible solutions for the given input instance. It may also be an ongoing system or data structure that responds appropriately to a constant stream of input.

怎么定义一个计算问题？计算问题的文字规定（specification）是由前置条件 （preconditions ）和后置条件（postconditions）两部分组成，它们分别描述计算问题的合法输入和期望的输出。每一个输入实例都函数映射一个期望的输出。但不 是所有的计算问题的每一个输入实例有唯一的输出，像最优化问题，一个输入有多个输出，里边有一个最优的[注3]。

注3：Kemin said: b.有意思，“问题”的答案也有从无到有，从有到好的模式；而且可根据这个模式对“问题”分类。如，判定问题就是“有没有”，“有”了之后，答案是单值、 复合值还是有结构的值分出了数值问题和组合问题；“有”了之后再评价就是“好”的问题，单一好是最佳值问题；组合好是最优化问题。

Example: The sorting problem is defined as follows:

Preconditions: The input is a list of n values, including possible repetitions.

Postconditions: The output is a list consisting of the same n values in non-decreasing order.

An Abstract Data Type :

Computers use zeros and ones, ANDs and ORs, IFs and GOTOs. This does not mean that we have to. The description of an algorithm may talk of abstract objects such as integers, reals, strings, sets, stacks, graphs, and trees; abstract operations such as “sort the list,” “pop the stack,” or “trace a path”; and abstract relationships such as greater than, prefix, subset, connected, and child. To be useful, the nature of these objects and the effect of these operations need to be understood. However, in order to hide details that are tedious or irrelevant, the precise implementations of these data structure and algorithms do not need to be specified. For more on this see Chapter 3.

抽象数据类型：计算机使用最原始的数据（0和1）和操作（ANDs 、ORs、 IFs 和 GOTO）工作，但这并不意味着我们也要。算法可使用抽象的对象（像整数、实数、字符串、栈、图和树）、抽象的操作（像排序、弹出弹入、跟踪）和抽象的关 系（大于、先于、子集、连通和后代）进行描述。当然，这些抽象的东西最后还是要被转为计算机理解的原始形式，这是算法和数据结构具体实现的话题，第三章有 讲述。

Running Time :

It is not enough for a computation to eventually get the correct answer. It must also do so using a reasonable amount of time and memory space. The running time of an algorithm is a function from the size n of the input instance given to a bound on the number of operations the computation must do. (See Chapter 23.) The algorithm is said to be feasible if this function is a polynomial like Time(n) = O(n^2), and is said to be infeasible if this function is an exponential like Time(n) = O(2^n). (See Chapters 24 and 25 for more on the asymptotic of functions.)

To be able to compute the running time , one needs to be able to add up the times taken in each iteration of a loop and to solve the recurrence relation defining the time of a recursive program. (See Chapter 26 for an understanding of ∑( i=1,n) i = Θ(n^2),and Chapter 27 for an understanding of T(n) = 2T(n/2 ) +n = Θ(n logn).)

算法光能给出正确的计算结果是不够的，它必须在合理的时间和空间内完成才是有用的。为了估算算法的时间复杂度，必需合计循环内基本操作的次数（看26章并理解式子 ：∑( i=1,n) i = Θ(n^2) ） 和解出递归算法递归关系（看27章并理解式子：T(n) = 2T(n/2 ) +n = Θ(n logn)）。

Meta-algorithms :

Most algorithms are best described as being either iterative or recursive. An iterative algorithm (Part One) takes one step at a time, ensuring that each step makes progress while maintaining the loop invariant. A recursive algorithm (Part Two) breaks its instance into smaller instances, which it gets a friend to solve, and then combines their solutions into one of its own.

大部分算法都是迭代或递归的形式。迭代算法通过每步保持循环不变量而不断向前推进，最终达到目标状态，解决问题；递归算法则把问题分解为相同结构规模小一点的问题，并通使用一些辅助的算法解决小问题，最后合并为一个解决方案。

Optimization problems (Part Three) form an important class of computational problems. The key algorithms for them are the following.

最优化问题是计算问题中最重要的一类，本书中涉及的最优化算法有：贪心算法、回溯算法、动态规划、归约算法和随机算法。

Greedy algorithms (Chapter 16) keep grabbing the next object that looks best.

Recursive backtracking algorithms (Chapter 17) try things and, if they don't work, backtrack and try something else.

Dynamic programming (Chapter 18) solves a sequence of larger and larger instances, reusing the previously saved solutions for the smaller instances, until a solution is obtained for the given instance.

Reductions (Chapter 20) use an algorithm for one problem to solve another.

Randomized algorithms (Chapter 21) flip coins to help them decide what actions to take. Finally, lower bounds

(Chapter 7) prove that there are no faster algorithms.