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