前言：此类型的文章皆为本人在阅读此书后给出的关于此书的理解，以及知识的梳理复习。若对文章有不解之处，或者文章有错欢迎评论区留言。
1.1 本书讨论的内容
有一组N个数，要找出其中第k个最大者，我们称之为选择问题(selection problem)。一种解法是将这N个数读进一个数组中，通过简单的算法如冒泡排序以递减顺序排序，则第k个位置即是要找的数。一个递减排序的冒泡排序，从最后一位开始把最大的向前放置。
void BubbleSort(int arr[], int size)
{int i, j, tmp;for (i = 0; i < size - 1; i++)for (j = size - 1; j > i; j--){if (arr[j] > arr[j - 1]){tmp = arr[j];arr[j] = arr[j - 1];arr[j - 1] = tmp;}}
}还有一种排序保证前 i+2 个元素为递减顺序，遇到下一个元素时将其排到正确的位置。
void BubbleSort(int arr[], int size)
{int i, j, tmp;for (i = 0; i < size - 1; i++)for (j = i; j >= 0; j--){if (arr[j] < arr[j + 1]){tmp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tmp;}}
}·由此可以引出一种稍微好点的算法，先把前k个元素读入数组并递减排序，接着在将剩下的元素逐个读入。当读取新元素时，如果它小于数组中第k个元素则忽略，否则就将其放到数组中正确的位置上，同时挤出那个位置上的元素。当算法结束时，第k个位置上的元素即作为答案返回。
这两种算法都很简单，此时要问哪个算法更好？哪个更重要？使用100万个元素的随机文件，在k=5000000的条件下模拟发现，两个算法在合理时间都不能结束。处理若干天才能完成。第7章将给出一个在1秒左右解决问题的算法。可以发现这两种算法相比于后者都是不切实际的。
第二个问题是解决字谜。输入由含字母的二维数组和单词列表组成，目标是找出字谜中的单词，单词可以水平、垂直或者沿对角线。如图
| 1 | 2 | 3 | 4 | |
| 1 | t | h | i | s |
| 2 | w | a | t | s |
| 3 | o | a | h | g |
| 4 | f | g | d | t |
该字谜由单词 this、two、fat 和 that组成。this从(1,1)到(1,4)。two从(1,1)到(3,1)。
现在有两种直观算法求解该问题。对单词表中的每个单词，检查有序三元组（行，列，方向）来验证这个单词是否存在。这需要大量嵌套的for循环。
或者，对于每个尚未进行到字谜最后的有序四元组（行，列，方向，字符数）测试所指的单词是否在单词表中。也会导致大量嵌套的for循环。
两种方法都不难编码，而且课求解许多现实的字谜游戏。然而若把字谜变为只给出谜板，而单词表基本上是一本英语词典，则上面两种解法需要相当多的时间。故这两种方法也不可接收，不过这样的问题还是有可能在数秒内解决的。
在许多问题中，有一个重要观念是：写出可以工作的程序还不够，如果此程序在巨大的数据集中运行，那么运行时间就成了很重要的问题。我们将在本书中看到对于大量的输入如何估计程序运行时间，尤其是如何在未具体编码时比较两个程序的运行时间。还将看到彻底改进程序速度以及确定瓶颈的方法。
1.2 数学知识复习
1.2.1 指数 - 略
1.2.2 对数 - 略，但需注意计算机科学中，除非有特别声明，所有的对数都是以2为低的。
1.2.3 级数 - 略
1.2.4 模运算
如果A-B能被N整除，那么我们就说A与B模N同余(congruent)，记作A ≡ B(mod N)。换句话说就是 A除以N的余数 和 B除以N的余数 相同即 A mod N = B mod N。于是，81 ≡ 61 ≡ 1(mod 10)跟等号情形一样，若A ≡ B(mod N)，则有 A+C≡B+C(mod N) 和 AD ≡ BD(mod N)。
1.2.5 证明方法
证明数据结构分析中的结论最常用的两个方法是归纳法和反正法。
归纳法证明
归纳法的证明有两个标准部分，一是证明 基准情形(base case)，就是确定定理对某个小的值的正确性。二是 归纳假设(inductive hypothesis)。假设定理到某个有限数k的所有情况都是成立的，然后再证明定理对下个值（通常为k+1）也成立。
以斐波那契数列为例 ，
，
，
，
，……，
，证明对
有
。基准情形有
，
。假设对于
，成立，这就是归纳假设。现在需要证明
。根据定义我们有
。则
化简后得
可得。也即证明完成，由于打印在文章中的证明难以阅读，之后的许多证明将不再进行，定理将会直接给出，有兴趣的读者可自行看书或查找资料。
定理1.3 如果 ，则
。
同样用归纳法可以证明。
反证法证明
反证法是先假设定理不成立，然后得出与已知条件不符合的结论，从而说明定理不成立的假设是错的。一个经典例子是 证明存在无穷多个素数。为证明它，先假设定理不成立，那么就由此假设引出了一个已知条件，即存在某个最大素数，令
是依序排列的所有素数。令数
，那么显然
，而
都不能整除
，因为每一个整数，或者是素数，或者是素数的乘积，显然
不是素数的乘积，那么
是素数与已知条件不符，因此，
是最大的素数的原假设不成立，也就是定理 存在无穷多个素数成立。
1.3 递归简论
数学函数有时以不太标准的形式定义。作为一个例子，在非负整数集上定义一个函数，它满足
且
。当函数用它自己来定义时就称为递归的(recursive)。但重要的是要记住，C提供的是遵循递归思想的一种企图。不是所有数学函数都能有效的（或正确地)由C的递归模拟实现。下图给出函数
的递归实现。
int F(int x)
{if (x == 0)return 0;elsereturn 2 * F(x - 1) + x * x;
}函数内，前两行处理基准情形，即此时可以直接算出函数值而不递归。就像如果没有“”这个条件，“
”在数学上就没有意义一样，在C中递归函数若没有基准情形，也是没意义的。
关于递归，有几个重要且可能会搞混的地方。一是它是否就是 循环逻辑(circular logic)?答案是：虽然用了函数本身去定义函数，但并未用函数本身定义该函数的一个特定的实例，也就是说用F(5)得到F(5)的值才是循环的。通过使用F(4)得到F(5)的值不是循环的，除非F(4)的求值又要用到对F(5)的计算。
假设以参数3调用函数，则要计算
，就要调用
，那么又要计算
，此时要计算
，我们先知道了
，这属于基准情形，然后就会得到
从而得到
，否则将一直递归下去。接下来看一个无终止递归程序
int Bad(unsigned int x)
{if (x == 0)return 0;elsereturn Bad(x / 3 + 1) + x - 1;
}乍一看貌似给出了x==0的基准情形，但实际上分析后发现 函数无法到达基准情形。由于x是无符号数，所以 ，则
，也就是说除非我们给的参数是0（一开始就是基准情形），否则就会开始递归调用，一旦开始递归调用就永远达不到基准情形了。其实错误点在于此函数将Bad(1)定义为Bad(1)，而Bad(1)究竟是多少，此定义给不出任何线索。
经过上述讨论，递归有两个基本法则：
1.基准情形(base case) 必须有不用递归就能求解的基准情形
2.不断推进(making progress) 对需要递归求解的情形，递归调用必须能够朝着产生基准情形的方向推进
作为一个非数学应用的例子，考虑查词典的情况，当查一个词的时候，词的解释中又有我们不认识的词，那么就不得不再去查这些词，当我们查到某一处，明白解释中的所有单词，然后按照查的顺序去理解之前的词，要么需要解释的词之间形成了循环解释，又或者解释中需要我们理解的某个单词不在这本词典里。
理解其递归策略：若知道一个单词的含义，就成功，否则就去查找这个词。如果理解该词解释中的所有单词，就又算我们成功。否则，递归地查找不认识的单词来解释们要么词典编纂的完美无暇，那么这个过程能够终止；如果其中一个单词没查到或是形成循环定义（解释）
，那么此过程循环不定。
打印输出数
假设我们有一个正整数N并希望把它打印出来，且现在有一个现有的例程只能处理单个数字，如PrintDigit(4)输出一个"4"。
递归对该问题提供了简洁的解。为打印"76234",先要打印"7623"，在打印"4"。第二步用PrintDigit(N%10)能够完成，而第一步打印“7623”实际上和原问题是同一个问题，因此可以递归的解决它。
我们还需要确定程序不是循环不定的，由于我们尚未定义一个基准情形，因此还有事情要做。如果，基准情形就是PrintDigit(N)。现在PrintOut已对从0到9的正整数定义，更大的通过较小的正整数定义，因此不存在循环定义。
void PrintOut(unsigned int N)
{if (N >= 10)PrintOut(N / 10);PrintDigit(N % 10);
}递归和归纳
定理1.4 对于,数字递归打印算法是正确的。
后记：我的初衷是想把书中涉及到的每一个细节都写出来，但是发现费时费力低效。因此之后的章节将只写出我认为的重点和理解，书中一些细节讨论不再机械地复述。
