ch1 绪论

1. 计算

【计算】即信息处理，指借助某种工具，遵照一定规则，以明确而机械的形式进行。

【计算模型】即计算机，指信息处理工具。

【算法】即特定计算模型下，旨在解决特定问题的指令序列。

• 输入：待处理的信息（问题）
• 输出：经处理的信息（答案）
• 正确性：的确可以解决指定的问题
• 确定性：可描述为一个由基本操作组成的序列
• 可行性：每一基本操作都可实现，且在常数时间内完成
• 有穷性：对于任何输入，经有穷次基本操作，都可以得到输出

【算法评价】

• 正确：符合语法，能够编译、链接，能够正确处理各种情况下的输入
• 健壮：能辨别不合法的输入并做适当处理，而不致非正常退出
• 可读：结构化 + 准确命名 + 注释 + ...
• 效率：速度尽可能快，存储空间尽可能少

2. 计算模型

为了客观评价算法的优劣，需要抽象出一个理想的平台或模型，不再依赖特定算法、特定问题等具体因素，从而直接准确地描述、测量并评价算法。

用 \(T_A(n)\) 表示算法 \(A\) 在求解某一问题规模为 \(n\) 的实例，所需的计算成本，讨论特定算法 \(A\) 时，可简记为 \(T(n)\)。稳妥起见，取 \(T(n) = \max\{T(P) | |P|=n\}\)，即，在规模同为 \(n\) 的所有实例中，只关注最坏者（成本最高）。

3. 渐进复杂度

当问题规模足够大之后，我们更关心计算成本的增长趋势。定义 \(T(n) = \cal{O}(f(n))\) 表示渐进时间复杂度上界，\(\forall n >> 2\)，\(\exists c> 0\) 使得 \(T(n)< c\cdot f(n)\)。通常用 \(T(n) = \Omega(f(n))\) 表示时间复杂度下界，\(T(n) = \Theta(f(n))\) 表示平均时间复杂度。

• \(\cal{O}(f(n)) = \cal{O}(c\cdot f(n))\)
• \(\cal{O}(n^a + n^b) = \cal{O}(n^a)\)，\(a \ge b > 0\)

4. 复杂度分析

【两个主要任务】正确性（不变性 × 单调性）；复杂度。

【主要方法】迭代（级数求和）；递归（递归跟踪 + 递推方程）；实用（猜测 + 验证）。

【说明】\(\tt C\)++ 等高级语言的基本指令，均等效于常数条基本机器指令，在渐进意义下，二者大体相当。

【空间复杂度】除却输入数据，算法在执行过程中所使用的空间量，重复使用者，只计一次，通常不超过时间复杂度。

【减而治之】为求解一个大规模的问题，可以将其划分为两个子问题（其一平凡，另一规模缩减），分别求解子问题；再由子问题的解，得到原问题的解。

【分而治之】为求解一个大规模的问题，可以将其划分为若干子问题（通常两个，且规模大体相当），分别求解子问题；由子问题的解，合并得到原问题的解。