1 算法设计与分析的基本概念

1.1 算法

定义：算法是对特定问题求解步骤的一种描述，是有限指令序列，每条指令表示一个或多个操作。
特性：
- 有穷性：算法需在有限步骤和时间内结束。
- 确定性：指令无歧义，相同输入输出唯一。
- 可行性：操作可通过基本运算有限次实现。
- 输入：零个或多个输入，来自特定对象集合。
- 输出：一个或多个输出，与输入有特定关系。

1.2 算法设计

目标： correctness（正确性）、readability（可读性）、robustness（健壮性）、high efficiency（高效性）。
常用设计技术： divide and conquer（分治法）、dynamic programming（动态规划法）、greedy algorithm（贪心法）、backtracking（回溯法）、branch and bound（分支限界法）、probabilistic algorithm（概率算法）、approximation algorithm（近似算法）。

1.3 算法分析

定义：估算算法所需资源，主要有时间复杂度和空间复杂度。
重要性：帮助选择最高效的算法。

1.4 算法的表示

自然语言：易懂但易产生歧义，冗长。
流程图：直观易懂，但严密性和灵活性不足。
程序设计语言：可直接执行，但抽象性差，细节繁琐。
伪代码：结合自然语言和程序设计语言，简洁明了，适合表达算法逻辑，本章采用 C 语言表示算法。

2 算法分析基础

2.1 时间复杂度

时间复杂度分析用于评估算法的运行时间，主要分为三种情况：

最好情况：算法执行时间最少的情况。
最坏情况：算法执行时间最多的情况。
平均情况：算法的平均执行时间，计算公式为 $\sum_{i=1}^{m} p_i \cdot t_i$ ，其中 $p_i$ 是输入的概率， $t_i$ 是输入的执行时间，输入分为 m 类。

2.2 渐进符号

渐进符号用于描述函数的增长速率：

O 记号：表示算法运行时间的上界。
Ω 记号：表示算法运行时间的下界。
Θ 记号：同时表示算法运行时间的上界和下界。

2.3 递归式

递归式用于描述递归算法的时间复杂度。常见的求解方法包括：

展开法：通过逐层展开递归式，得到一个求和表达式，然后求解。
代换法：猜测解的形式，然后用数学归纳法证明。
递归树法：构造递归树，将递归调用的代价累加到递归树的每一层。
主方法：适用于形式为 T(n) = aT(n/b) + f(n) 的递归式，其中 a ≥ 1，b > 1，f(n) 是一个递增函数。

3 分治法

3.1 递归的概念

递归是函数直接或间接调用自身的一种方法。递归有两个基本要素：边界条件（决定递归何时终止）和递归模式（如何将问题分解为更小的子问题）。例如，阶乘函数可以用递归定义为：

$\begin{cases} 1 & \text{if } n = 0 \\ n \times (n-1)! & \text{if } n > 0 \end{cases}$

对应的 C 代码如下：

int Factorial(int n) {if (n == 0)return 1;elsereturn n * Factorial(n - 1);
}

3.2 分治法的基本思想

分治法的核心思想是将一个难以直接解决的大问题分解成规模较小的子问题，递归地解决这些子问题，然后将子问题的解合并成原问题的解。分治法在每一层递归上都有三个步骤：

分解：将原问题分解成多个较小的子问题。
求解：递归地求解各个子问题。若子问题足够小，则直接求解。
合并：将子问题的解合并成原问题的解。

3.3 分治法的典型实例

3.3.1 归并排序

归并排序是分治法的经典应用，其基本思想是将待排序元素分成大小大致相同的两个子序列，分别对这两个子序列递归地排序，最后将排好序的子序列合并成一个有序序列。

归并排序的时间复杂度为 $\log n)$ 。

3.3.2 最大子段和问题

给定一个由 n 个整数（可能有负整数）组成的序列 $a1,a2,…,ana_1, a_2, \ldots, a_n$ ，求该序列形如 $∑k=ijak\sum_{k=i}^j a_k$ 的子段和的最大值。最大子段和问题的分治法策略如下：

分解：将序列从中间位置分为两段，分别求出左半段和右半段的最大子段和。
求解：递归地求解左半段和右半段的最大子段和。
合并：比较左半段、右半段和跨越中间位置的子段和的最大值，取三者中的最大值作为原问题的解。

4 动态规划法

4.1 动态规划法的基本思想

动态规划法与分治法类似，基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的，而是具有重叠子问题的性质。因此，动态规划法通过记录已经求解过的子问题的解（通常用表格记录），以避免重复计算，从而提高效率。

动态规划法通常用于求解具有某种最优性质的问题，通过以下步骤实现：

找出最优解的性质，并刻画其结构特征。
递归地定义最优值。
以自底向上的方式计算最优值。
根据计算最优值时得到的信息，构造一个最优解。

当只需要求出最优值时，步骤（1）-（3）是动态规划算法的基本步骤。若需要构造最优解，则必须执行步骤（4）。

4.2 动态规划法的典型实例

4.2.1 0-1 背包问题

动态规划法通过以下步骤解决 0-1 背包问题：

刻画 0-1 背包问题的最优解结构
递归定义最优值
计算背包问题的最优值
根据最优解构造最优解

4.2.2 最长公共子序列（LCS）问题

LCS 问题的最优子结构
递归定义最优值
计算最优值
构造最优解

5 贪心法

5.1 贪心法的基本思想

贪心法是一种算法设计技术，常用于解决优化问题。与动态规划法不同，贪心法通过一系列局部最优选择来构建全局最优解。贪心法的特点如下：

局部最优选择：贪心法在每一步选择中都做出局部最优的选择，而不从全局考虑。这种局部最优选择并不能保证总能得到全局最优解，但在许多情况下可以得到较好的近似解。
不可回溯性：一旦做出选择，就不会再改变，即使后续发现有更好的选择也不会回溯。

贪心法适用的问题通常具有以下两个重要性质：

最优子结构：问题的最优解包含其子问题的最优解。
贪心选择性质：问题的整体最优解可以通过一系列局部最优选择得到。

5.2 贪心法的典型实例

5.2.1 活动选择问题

活动选择问题要求从多个活动集合中选择最大数量的相容活动。贪心算法通过按活动结束时间排序，每次选择最早结束的活动，并跳过与之冲突的活动。

5.2.2 背包问题

背包问题允许将物品部分装入背包，目标是使背包中物品的总价值最大。贪心策略包括：

按最大价值优先：先放入价值最大的物品。
按最小重量优先：先放入重量最小的物品。
按最大单位重量价值优先：先放入单位重量价值最大的物品。

贪心算法的 C 代码如下：

float* GreedyKnapsack(int n, int W, int* Weights, float* Values, float* V) {float* x = (float*)malloc(sizeof(float) * n);for (int i = 0; i < n; i++)x[i] = 0;for (int i = 0; i < n; i++) {if (Weights[i] <= W) { // 如果背包剩余容量可以装下该物品x[i] = 1;W -= Weights[i];} elsebreak;}if (i < n) { // 如果还有物品可以部分装入背包x[i] = (float)W / Weights[i];}return x;
}