解决计算问题（Solve）#

例如：给定一个数组，找到某个数字的位置，判断一群人是否有相同生日，给定地图，寻找最短路径等，这些都是计算问题。

证明正确性（Correctness）#

为什么这个算法一定正确？

测试不能证明所有情况，算法理论要求对任意规模、任意输入，都能证明它正确。

分析效率（Efficiency）#

同一个问题可能有很多算法，算法研究关心哪一个更高效。

数学归纳法#

归纳法（Induction）是一种证明方法，用来证明一个命题对于无限多个自然数情况都成立。

数学归纳法的本质可以浓缩为：

它深刻依赖自然数的递推性与良序性，是数学、算法设计、计算机科学中证明递归结构和无限过程的工具之一。

1. 数学归纳法的基本形式

假设有一个关于自然数 $n$ 的命题 $P(n)$。例如我们要证明等差数列求和公式：

目标是证明：对于所有 $n \geq 1$，命题 $P(n)$ 都成立。

数学归纳法要求完成以下两个核心步骤：

第一步：归纳基础（Base Case）

证明命题在第一个自然数处成立。先令 $n=1$：

左边： $1$

右边： $\frac{1(1+1)}{2} = 1$

左边 = 右边，因此 $P(1)$ 成立。

第二步：归纳假设与递推（Inductive Step）

假设命题对某个具体的自然数 $k$ 成立，即假设 $P(k)$ 成立：

然后利用这个假设，去证明 $P(k+1)$ 也成立。即证明：

推导过程如下： 左边前 $k$ 项可以利用归纳假设进行替换：

提取公因式 $(k+1)$：

通分整理：

推导出的结果正好是 $P(k+1)$ 的右边式子。因此，$P(k+1)$ 成立。

2. 归纳法的完整逻辑

数学归纳法实际上证明了 $P(1)$ 成立，并且 $P(k) \Rightarrow P(k+1)$ 成立，从而得出结论：对于所有正整数 $n$，$P(n)$ 都成立。

写成严谨的数理逻辑形式如下：

为什么这能证明无限多个情况？关键在于形成了一个无限传递链：

1. 因为 $P(1)$ 成立，且 $P(1) \rightarrow P(2)$，所以 $P(2)$ 成立。
2. 因为 $P(2)$ 成立，且 $P(2) \rightarrow P(3)$，所以 $P(3)$ 成立。
3. 继续传递：$P(3) \rightarrow P(4)$，于是 $P(4)$ 成立……

最终，虽然我们无法用穷举法去逐个证明无限多个情况，但归纳步骤自动覆盖了 $P(1), P(2), P(3), \dots, P(n)$ 乃至无穷远。

3. 数学归纳法的两个基本性质

性质 1：递推性

归纳法依赖于 $P(k) \rightarrow P(k+1)$，也就是说：当前情况成立，可以推出下一情况成立。 它描述的是命题之间连续递进的逻辑关系。

性质 2：完备性

自然数集合 $\mathbb{N} = \{1, 2, 3, \dots\}$ 具有一个重要性质：

自然数的良序原理（Well-ordering Principle）：任意非空自然数集合都有最小元素。

归纳法证明生日算法的步骤：

1. 归纳基础（Base Case） ：面试0个学生时，不可能有匹配，算法正确返回空值（谓词自然成立）。

2. 归纳假设（Inductive Hypothesis） ：假设在面试前 $k$ 个学生后，如果其中有匹配项，算法已经正确返回，如果没有，记录本包含了这 $k$ 个人的生日。

3. 归纳递推（Inductive Step） ：考虑第 $k+1$ 个学生。分三种情况讨论：

   1. 前 $k$ 个人中已有匹配（根据假设，算法已正确返回）。

   2. 前 $k$ 个人无匹配，但第 $k+1$ 个人与前面的人有匹配（算法通过比对记录本会找到并返回）。

   3. 若均无匹配，将第 $k+1$ 个人加入记录，假设对 $k+1$ 依然成立。