第一章 引论 -- 数据结构与算法分析

数学知识

指数

\[ X^AX^B=X^{A+B} \] \[ \frac{X^A}{X^B} = X^{A-B} \] \[ (X^A)^B = X^{AB} \] \[ X^N+X^N={2X^N}\neq{X^{2N}} \] \[ 2^N + 2^N = 2^{N+1} \]

对数

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

更多关于对数: http://zh.wikipedia.org/wiki/%E5%AF%B9%E6%95%B0

级数

更多关于级数: http://zh.wikipedia.org/wiki/%E7%BA%A7%E6%95%B0

最容易记忆的公式是

\[ \sum_{i=0}^{N}{2^i} = 2^{N+1} - 1 \]

\[ \sum_{i=0}^{N}{A^i} = \frac{A^{N+1} - 1}{A - 1} \]

在第二个公式中, 如果 0 < A < 1, 则

\[ \sum_{i=0}^{n}{A^i}\le{\frac{1}{1-A}} \]

另任何这样的级数都可以通过最基本的公式计算其值

\[ \sum_{i=1}^{N}{i} = \frac{N(N + 1)}{2}\approx{\frac{N^2}{2}} \]

下面是一些不太常见的公式

\[ \sum_{i=1}^{N}{i^2} = \frac{N(N + 1)(2N + 1)}{6} \approx{\frac{N^3}{3}} \] \[ \sum_{i=1}^{N}{i^k} \approx{\frac{N^{k+1}}{|k + 1|}}k \neq{-1} \]

当 \( k = -1 \) 时, 后一个公式是不成立的, 此时我们需要下面的公式. 数 \( H_N \)叫做调和数, 其和叫做调和和. 下面近似式的误差趋向于 \( \gamma \approx{0.57721566} \), 这个值被称为欧拉常数 (Euler's constant)

\[ H_N = \sum_{i=1}^{N}{\frac{1}{i}} \approx{log_{e}N} \]

以下两个公式只不过是一般的代数运算

\[ \sum_{i=1}^{N}{f(N)} = Nf(N) \] \[ \sum_{i=n_0}^{N}{f(i)} = \sum_{i=1}^{N}{f(i)} - \sum_{i=1}^{n_{0} - 1}{f(i)} \]

模运算

如果 N 整除 A - B, 那么我就说 A 与 B 模 N 同余(congruent), 记为 \( A \equiv{B}(mod N) \) 也就是 A 和 B 去对 N 整除, 所得的余数都是相同的: \( 81 \equiv{61} \equiv{1} (mod 10 ) \)

如同等号的情形一样, 若 \( A \equiv{B} ( mod N ) \), 则 \( A + C \equiv{B + C} (mod N)\)

以及 \( AD \equiv{BD} ( mod N ) \)

证明方法

归纳法证明

归纳法进行证明有两个标准部分. 第一步是 基准情形(base case), 就是确定 定理对某个(某些)小的(通常是退化的)值的正确性

接着, 进行 归纳假设(inductive hypothesis). 一般说来, 这意味着假设定理对 直到某个有限数 \(k\) 的所有情况都是成立. 然后使用这个假设证明定理对下一个值 (通常是 \( k + 1\) )也是成立的. 至此定理得证(在 \(k\) 是有限的情形下)

例子

反证法证明

反证法证明是通过假设定理不成立, 然后证明该假设导致某个已知的性质不成立, 从而说明原假设是错误的.

一个经典的例子是说明存在无穷多个素数. 为了证明这个结论, 我们假设定理不成立. 于是, 存在某个最大的素数 \(P_k\). 令 \(P_1, P_2, ..., P_k\)是依序排列的所有素数 并考虑

\[ N = P_{1}P_{2}P_{3}...P_{k} + 1 \]

显然, N 是比 \( P_k \) 大的数, 根据假设 N 不是素数. 可是, \(P_{1}, P_{2}, ..., P_{k}\) 都不能整除 N, 以为除的的结构总有余数 1. 这就产生 一个矛盾, 因为每一个整数或者是素数, 或者是素数的乘积. 因此, \( P_k \) 是最大素数的假设是不成立的, 这整以为着定理成立

递归简论

华氏温度转换成摄氏温度

\[ C = \frac{5(F - 32)}{9} \]

有了这个公式, 写一个 C 函数就太简单了.

当一个函数用它自己来定义时就称为 递归(recurive) 的.

递归绝不应该作为简单 for 循环的代替物

递归的基本法则:

  1. 基准情形(base case). 必须要有不用递归就能求解的情形.
  2. 不断推进(making progress). 递归调用必须朝基准情形不断推进.
  3. 设计法则(design rule). 假设所有的递归调用都能运行.
  4. 合成效益法则(compound interest rule). 求解同一问题的统一实例, 切勿在不同的递归调用中做重复性的工作.