算法问题求解基础

算法是强调精确定义的结构化过程，并且因为这个特点把计算机科学和理论数学区分开来。

理解问题

从实践的观点来看，设计一个算法前的第一件事是完全理解所给出的问题。仔细阅读问题的描述，提出疑问，手工处理一些小例子，考虑特殊情况，再继续提问。

有几类问题频繁出现在计算机应用中，待解决问题属于其中一类，我们就用一个已经的算法来求解。

本节简要介绍自己设计算法一系列步骤。

算法的输入，确定了该算法所解问题的一个实例. 严格确定算法处理实例的范围，不要试图略去算法解题步骤的第一步。

了解计算设备的性能

完全了解了待处理问题后，我们要了解将要运行算法的计算设备的性能。今天大多数算法要靠运行于冯·诺伊曼机器上的代码来实现。这个饿体系结构的重要用于随即存取机（random-access machine, RAM）。最主要设想是：指令逐条运行，每次执行一步操作。相应地，设计运行于这种机器上的算法称为顺序算法.

更新式的计算机可在同一时间执行多条操作，即并行计算。它们已经不满足RAM模型的核心假设饿，能够利用这种计算性能优势的算法称为并行算法.学习RAM模型下算法设计和分析的经典技术仍然是算法学的基石。

我们的算法不需要考虑计算机的计算速度和存储容量。很多情况下，我们并不需要担心计算机的速度无法胜任所要处理的任务。

在精确解法和近似解法间做选择

为什么有时我们会选择近似算法呢？

首先，有一些重要的问题的确无法求得精确解。其次，由于某些问题固有的复杂性，已经的精确算法来解决俄该问题会慢得无法忍受。

确定适当的数据结构

有些算法的确需要基于一些精心设计的数据结构。

第6章的变治法和第7章的时空权衡所讨论的一些算法设计技术紧密地依赖对问题实例的数据进行构造和重构。

算法设计技术

理解问题，了解计算设备性能，在精确解法和近似解法间做选择，确定适当的数据结构这些算法的必要条件已经具备了。如何设计一个算法来解决给定问题呢？这正是本书希望解答的主要问题，我们讲授一些一般性的设计方法。

什么是算法设计技术呢？

算法设计技术（也称为“策略”或者“范例”）是用算法解题的一般性方法，解决不同计算领域的多种问题。

本书目录中的多数章节致力于介绍某个单独的设计技术，提取出对算法非常有用的关键思想。

详细表述算法的方法

一旦设计了一个算法，需要用一定的方式对其进行详细描述。比如文字和伪代码描述算法。

伪代码是自然语言和类编程语言组合的混合结构，描述更精确，更简洁。

流程图已经被淘汰。

程序当作一种算法的实现。

证明算法的正确性

完成了算法的描述，必须证明它的正确性。

对于每一个合法输入，算法都会在有限的时间内输出一个满足要求的结果。举例来说，计算最大公约数的欧几里德算法的正确性基于等式gcd(m, n) = gcd(n, m mod n)的正确性。该算法每做一次循环，第二个数字变得更小的观察结果。以及算法会在第二个数字变为0时停止的事实。

正确性的一般方法时使用数学归纳法。

根据一些特定的输入来追踪算法操作的做法很有意义，虽然不能最终证明该算法的正确性，但是可以发现算法不正确。

分析算法

我们希望我们的算法具有特性。除正确性意外，最重要的特性就是“效率”。

算法有两种效率：时间效率和空间效率。时间效率显示了算法运行得多快;空间效率显示了算法需要多少额外的存储空间。

算法具有简单性。简单的算法易于理解和实现，相应的程序也往往包含较少的Bug。

另一个算法的特性是一般性。有时候以更一般的形式出现的问题，反而更容易解决。考虑一个判断两个整数是否互质问题的例子，即它们两个是否只拥有唯一的公约数上。实际上这样做更容易：设计一个更一般的算法，用于计算两个整数的最大公约数，然后解决前面的问题——检查一下最大公约数是否为1.然而，有些情况下，设计一个更一般的算法不仅没有必要，甚至可能是困难的。

我们设计的算法，能够在手头的可能涉及的输入范围内作恰当的处理。

如果我们对于某个算法的效率，简单性或一般性不满意，则必须回到设计台，重新设计算法。其实，即使我们对算法作出了肯定的评价，再去探寻另一种算法仍然是有意义的。

有道是：“不是在无以复加，而是在无以复减的时候，设计师才直到他已经到达了完美的境界。”

为算法写代码

算法注定要以计算机程序的形式实现。

对计算机程序做测试与其说是一门科学，不如说是一门艺术。无论我们实现何种算法，都要对程序进行彻底的测试及调试。

另一个需要注意的问题是，本书自始至终都假设算法的输入都落入实现确定的范围，从而不进行检验。当算法的程序实现用于实际应用时，我们还是需要提供这样的检验的。

我们需要掌握一些技巧，比如：在循环之外计算循化中的不变式；合并公共的子表达式；开销低的操作代替开销高的操作等等。

运行中的程序为我们提供了一个分析它内在算法的额外机会。这种分析基础是，针对若干输入对程序计时，然后分析所获得的结果。

作为一个规律，一个好的算法是反复努力和重新修正的结果。

不可判定的问题不能用算法解决。

发明或者发现算法是一个非常有创造性和非常值得付出的过程。