第1章 引论

前言

        这一章，阐述本书的目的，并简要复习离散数学以及程序设计的一些概念：

• 看到程序在较大输入情况下的运行性能与在适量输入情况下的运行性能具有同等重要性
• 总结本书其余部分所需要的数学基础
• 简要复习递归

---

1.1 本书讨论的内容

        在许多问题当中，一个重要的观念是：写出一个可以工作的程序并不够。如果这个程序在巨大的数据集上运行，那么运行时间就变成了重要的问题。我们将在本书中看到对于大量的输入如何估计程序的运行时间，尤其是如何在尚未具体编码的情况下比较两个程序的运行时间。我们还将看到彻底改进程序速度以及确定程序瓶颈的方法。这些方法将使我们能够找到需要大力优化的那些代码段。

1.2 数学知识复习

        本节列出一些需要记住或是能够推导出的基本公式，复习基本的证明方法

1.2.1 指数

1.2.2 对数

        在计算机科学中，除非有特别的声明，所有的对数都是以2为底的

定义：当且仅当，

由该定义得到几个方便的等式：

定理1.1

；

定理1.2

其他有用的公式

（对所有的成立）

，，，

1.2.3 级数

几何级数

收敛级数

算数级数

；

        数叫作调和数，其和叫作调和和。以下近似式中的误差趋向于，这个值称为欧拉常数（Euler's constant）

代数运算

1.2.4 模运算

        如果整除，那么我们就说与模同余(congruent)，记为。直观地看，这意味着无论还是除以，所得余数都是相同的。于是，。如同等号的情形一样，若，则以及。
        有许多定理适用于模运算，其中有一些特别要用到数论来证明。我们将谨慎地使用模运算，这样，前面的一些定理也就足够了。

1.2.5 证明方法

        证明数据结构分析中的结论的两个最常用的方法是归纳法和反证法(偶尔也被迫用到只有教授们才使用的证明方法)。证明一个定理不成立的最好方法是举出一个反例。

        归纳法证明
        由归纳法进行的证明有两个标准的部分。第一步是证明基准情形(base case)，就是确定定理对于某个(某些)小的(通常是退化的)值的正确性，这一步几乎总是很简单的。接着，进行归纳假设(inductive hypothesis)。一般说来，这意味着假设定理对直到某个有限数的所有情况都是成的。然后使用这个假设证明定理对下一个值(通常是)也是成立的。至此定理得证(在有限的情形下)。

定理1.3   如果，则

        通过反例证明
        公式不成立。证明这个结论最容易的方法就是计算。

        反证法证明
        反证法证明是通过假设定理不成立，然后证明该假设导致某个已知的性质不成立，从而说明原假设是错误的。一个经典的例子是证明存在无穷多个素数。为了证明这个结论，我们假设定理不成立。于是，存在某个最大的素数。令是依序排列的所有素数并考虑

        显然，是比大的数，根据假设不是素数。可是，都不能整除，因为除得的结果总有余数1。这就产生一个矛盾，因为每一个整数或者是素数，或者是素数的乘积。因此，是最大素数的原假设是不成立的，这正意味着定理成立。

1.3 递归简论

        我们熟悉的大多数数学函数是由一个简单公式描述的。例如，我们可以利用公式

C=5(F−32)/9" role="presentation">C=5(F−32)/9$\mathit{C}\mathit{=}\mathit{5}\mathit{(}\mathit{F}\mathit{-}\mathit{32}\mathit{)}\mathit{/}\mathit{9}$

把华氏温度转换成摄氏温度。有了这个公式，写一个C函数就太简单了。除去程序中的说明和大括号外，将一行公式翻译成一行C程序。
        有时候数学函数以不太标准的形式来定义。作为一个例子，我们可以在非负整数集上定义一个函数，它满足且。从这个定义我们看到，，，以及。当一个函数用它自己来定义时就称为是递归的(recursive)。C允许函数是递归的。但重要的是要记住，C提供的仅仅是遵循递归思想的一种企图。不是所有的数学递归函数都能有效地(或正确地)由C的递归模拟来实现。上面例子说的是递归函数应该只用几行就能表示出来，正如非递归函数一样。图1-2给出了函数的递归实现。

int F(int X)
{
    if(X == 0)
        return 0;
    else
        return 2 * F(X - 1) + X * X;
}

        第一行和第二行处理基准情形，即此时函数的值可以直接算出而不用求助递归。正如若没有“”这个条件“”在数学上没有意义一样，C的递归函数若无基准情形，也是毫无意义的。第三行执行的是递归调用。

        关于递归，有几个重要并且可能会被搞混的地方。一个常见的问题是：它是否就是循环逻辑(circular logic)？答案是：虽然我们定义一个函数用的是这个函数本身，但是我们并没有用函数本身定义该函数的一个特定的实例。换句话说，通过使用来得到的值才是循环的。通过使用得到的值不是循环的，除非的求值又要用到对的计算。
实际上，递归调用在处理上与其他的调用没有什么不同。如果以参数4的值调用函数，那么程序的第三行要求计算。这样，就要执行一个计算的调用，而这又导致计算。因此，又要执行另一个计算的调用，而这意味着必须求出的值。为此，通过计算而得到。此时，必须被赋值。由于这属于基准情形，因此我们事先知道。从而的计算得以完成，其结果为1。然后，、以及最后的值都能够计算出来。跟踪挂起的函数调用(这些调用已经开始但是正等待着递归调用来完成)以及它们中变量的记录工作都是由计算机自动完成的。然而，重要的问题在于，递归调用将反复进行直到基准情形出现。例如，计算的值将导致调用、等等。由于这将不可能出现基准情形，因此程序也就不可能算出答案。偶尔还可能发生更加微妙的错误，我们将其展示在图1-3中。图1-3中程序的错误是将第三行上的定义为。显然，实际上究竟是多少，这个定义给不出任何线索。因此，计算机将会反复调用以期解出它的值。最后，计算机簿记系统将占满空间，程序崩溃。一般说来，我们会说该函数对一个特殊情形无效，而在其他情形下是正确的。但此处这么说则不正确，因为
调用。因此，也不能求出值来。不仅如此，、和Bad(5)" role="presentation">Bad(5)$\mathit{B}\mathit{a}\mathit{d}\mathit{(}\mathit{5}\mathit{)}$都
要调用，的值算不出来，它们的值也就不能求出。事实上，除了0之外，
这个程序对任何的N都不能一步算出结果。对于递归函数，不存在像“特殊情形”这样的情况。

        上面的讨论导致递归的前两个基本法则：
1. 基准情形(base case)。必须有某些基准的情形，它们不用递归就能求解。
2.不断推进(making progress)。对于那些需要递归求解的情形，递归调用必须能够朝着产生基准情形的方向推进。

        在本书中我们将用递归解决一些问题。作为非数学应用的一个例子，考虑一本大词典。词典中的词都是用其他的词定义的。当我们查一个单词的时候，我们不理解对该词的解释，于是不得不再查出现在解释中的一些词。而对这些词解释中的某些词我们又不理解，因此还要继续这种搜索。因为词典是有限的，所以实际上，要么我们最终查到一处，明白此处解释中所有的单词(从而理解这里的解释，并按照查找的路径回头理解其余的解释)，要么我们发现这些解释形成一个循环，无法明白其中的意思，或者在解释中需要我们理解的某个单词不在这本词典里。
        理解这些单词的递归策略如下：如果我们知道一个单词的含义，那么就算我们成功；否则，我们就在词典里查找这个单词。如果我们理解该词解释中的所有单词，那么又算我们成功；否则，递归地查找一些我们不认识的单词来“算出”对该单词解释的含义。如果词典编纂得完美无瑕，那么这个过程就能够终止；如果其中一个单词没有查到或是形成循环定义(解释)，那么这个过程则循环不定。

        打印输出数
        设我们有一个正整数N并希望把它打印出来。我们的例程的名字为PrintOut(N)。假设仅有的现成I/O例程将只处理单个数字并将其输出到终端。我们将这个例程命名为PrintDigit，例如，PrintDigit(4)将输出一个“4”到终端。
        递归对该问题提供了一个非常简洁的解。为打印“76234”，需要首先打印出“7623”，然后再打印出“4”。第二步用语句PrintDigit(N%10)很容易完成，但是第一步却不比原问题简单多少。它们实际上是同一个问题，因此我们可以用语句PrintOut(N/10)递归地解决它。
        这告诉我们如何去解决一般的问题，不过我们仍然需要确认程序不是循环不定的。由于我们尚未定义一个基准情形，因此很显然，我们仍然还有些事情要做。如果0⩽N<10" role="presentation">0⩽N<10$\mathit{0}⩽\mathit{N}\mathit{<}\mathit{10}$，那么我们的基准情形就是PrintDigit(N)。现在，PrintOut(N)已对每一个从0到9的正整数做出定义，而更大的正整数则通过较小的正整数定义。因此，不存在循环定义。整个过程如图1-4所示。

void PrintOut(unsigned int N)
{
    if(N >= 10)
        PrintOut(N / 10);
    PrintDigit(N % 10);
}

        我们没有努力去高效地编写这个程序。我们本可以避免使用mod操作(它的耗费是很大的)，因为N%10 = N - [N/10] * 10
        递归和归纳
        我们将使用归纳法对上述数字递归打印程序给予更严格的证明。
定理1.4   对于，数字递归打印算法是正确的。
证明   (根据所含数字的位数，利用归纳法证明)：
首先，如果只有一位数字，那么程序显然是正确的，因为它只调用一次PrintDigit。然后，设PrintOut对所有位或位数更少的数均能正常工作。位的数字可以通过其前位数字后跟一位最低位数字来表示。前位数字形成的数恰好是[N/10]" role="presentation">[N/10]$\mathit{[}\mathit{N}\mathit{/}\mathit{10}\mathit{]}$，归纳假设它能够被正确地打印出来，而最后一位数字是，因此该程序能够正确打印出任意位数。于是，根据归纳法，所有的数都能被正确地打印出来。
        这个证明看起来可能有些奇怪，实际上相当于算法的描述。它阐述的是在设计递归程序时，同一问题的所有较小实例均可以假设运行正确，递归程序只需要把这些较小问题的解(它们通过递归奇迹般地得到)结合起来而形成现行问题的解。其数学根据则是归纳法。

我们给出递归的第三个法则：
3.设计法则(design rule)。假设所有的递归调用都能运行。这是一条重要的法则，因为它意味着，当设计递归程序时一般没有必要知道簿记管理的细节，不必试图追踪大量的递归调用。追踪实际的递归调用序列常常是非常困难的。当然，在许多情况下，这正体现了使用递归的好处，因为计算机能够算出复杂的细节。
        递归的主要问题是隐含的簿记开销。虽然这些开销几乎总是合理的(因为递归程序不仅简化了算法设计，而且也有助于给出更加简洁的代码)，但是递归绝不应该作为简单for循环的代替物。我们将在3.3节更仔细地讨论递归涉及的系统开销。

当编写递归例程的时候，关键是要牢记递归的四条基本法则：
        1. 基准情形。必须有某些基准的情形，它们不用递归就能求解。
        2. 不断推进。对于那些需要递归求解的情形，递归调用必须能够朝着产生基准情形的方向推进。
        3. 设计法则。假设所有的递归调用都能运行。
        4.合成效益法则(compound interest rule)。在求解一个问题的同一实例时，切勿在不同的递归调用中做重复性的工作。

        第四条法则的正确性将在后面的章节给予证明。使用递归来计算诸如斐波那契数之类简单数学函数的值的想法一般来说不是一个好主意，其根据正是第四条法则。只要在头脑中记住这些法则，递归程序设计就应该是简单明了的。