数据结构与算法分析读书笔记系列01-基础知识
1 基础知识
设一组N个数而要确定其中第k个最大者的问题。我们称之为选择问题（selection problem）。
该问题的一种解法就是将这N个数读进一个数组中，再通过某种简单的算法，比如冒泡排序法，以递减顺序将数组排序，然后返回位置k上的元素。稍微好一点的算法可以先把k个元素读入数组并（以递减的顺序）对其排序。接着，将剩下的元素再逐个读入。当新元素被读到时，如果它小于数组中的第k个元素则忽略，否则就将其放到数组中正确的位置上，同时将数组中的一个元素挤出数组。当算法终止时，位于第k个位置上的元素作为答案返回。
上面两种算法虽然都能算出结果，但在大数据量的情况下，这两种算法都是不切实际的。在许多问题当中，一个重要的观念是：写出一个可以工作的程序并不够。如果这个程序在巨大的数据集上运行，那么运行时间就变成了重要的问题。在这个系列中会看到对于大量的输入，如何估计程序的运行时间，尤其是如何在尚未具体编码的情况下比较两个程序的运行时间。我们还将看到彻底改进程序速度以及确定程序瓶颈的方法。这些方法将使我们能够找到需要大力优化的那些代码段。
2 数学知识和复习
2.1 指数
XA XB = X(A+B)
XA / XB = X(A-B)
(XA)B = X(AB)
XN + XN = 2XN ≠ X(2N)
2N + 2N = 2(N+1)
2.2 对数
在计算机科学中，除非有特别的申明，所有的对数都是以2为底的。
定义：XA = B ,当且仅当logX B = A
由改定义可以得到几个方便的等式。
定理1.1
logA B = logC B / logC A ; C > 0
定理1.2
logAB = logA + logB
2.3 级数
容易记忆的公式
∑i=0T 2i = 2(N+1)-1
和
∑i=0N Ai = (A(N+1) - 1)/(A-1)
在第二个公式中，如果0<A<1，则
∑i=0 Ai <= 1/(1-A)
当N趋向于∞时时改和趋向于1/(1-A)，这些公式是“几何级数”公式。
2.4 模运算
如果N整除A-B，那么我们就说A与B模N同余，记为A≡B(modN)。
2.5 证明方法
证明数据结构分析中的结论的两个最常用的方法是归纳法和反证法（偶尔也会被迫使用学术中才使用的证明方法）。证明一个定理不成立的最好的方法是举出一个反例。
2.5.1 归纳法证明
由归纳法进行的证明有两个标准的部分，第一部分是证明基准情形（base case），就是确定定理对于某个（某些）小的（通常是退化的）值的正确性；这一步几乎总是简单的。接着，进行归纳假设（inductive hypothesis）。一般来说，这意味着假设定理对直到某个有限数k的所有情况都是成立的。然后使用这个假设证明定理对下一个值（通常k+1）也是成立的，至此定理得证（在k是有限的情形下）。
2.5.2 反证法证明
反证法证明是通过假设定理不成立，然后证明改假设导致某个已知的性质不成立，从而说明原假设是错误的。
3 递归简论
当一个函数用它自己来定义时就称为递归（recursive）的。
递归的四条基本法则：
- 基准情形 。必须总有某些基准情形，它无须递归就能解出。
- 不断推进 。对于那些需要递归求解的情形，每一次递归调用都必须要使求解状况朝接近基准情形的方向推进。
- 设计法则 。假设所有的递归调用都能运行。
- 合成效益法则（compound interest rule） 。在求解一个问题的同一实例时，切勿在不同的递归抵用中做重复的事。
4 总结
对于面临大量输入的算法，它所花费的时间是个判断其好坏的重要的标准。（当然正确性是最重要的。）速度是相对的。对于一个问题在一台机器上是快速的算法有可能对另一个问题或在不同的机器上就变成了慢的。