数据结构与算法分析 —— C 语言描述：引论

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

数学知识复习

指数

对数

定义：当且仅当 。推导可得：

级数

如果 0 < A < 1

否则

模运算

如果 N 整除 A - B，那么我们就说 A 与 B 模 N 同余（congruent），记为 (mod N)。直观地看，这意味着无论 A 还是 B 除以 N，所得余数都是相同的。于是，。如同等号的情形一样，若 (mod N)，则 以及 。

证明方法

• 归纳法证明：第一步是证明基准情形（base case），就是确定定理对于某个（某些）小的（通常是退化的）值的正确性，这一步几乎总是很简单的。接着，进行归纳假设。一般来说，这意味着假设定理对直到某个有限数 k 的所有情况都是成立的。然后使用这个假设证明定理对下一个值（通常是 k + 1）也是成立的。至此定理得证（在 k 有限的情形下）。
  • 定理：如果 ，则 。
• 通过反例证明：反证法证明是通过假设定理不成立，然后证明该假设导致某个已知的性质不成立，从而说明原假设是错误的。

递归简论

递归的四条基本法则

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