算法基础

算法（Algorithm）是解决问题的关键工具，是计算机科学的核心概念。本章从离散数学的角度讨论算法的基本性质、复杂度分析以及正确性证明。理解算法的数学基础，是掌握程序设计和问题求解能力的前提。

算法的概念

什么是算法？

算法是一个有限指令序列，用于执行特定计算或解决特定问题。这个词源于波斯数学家 Al-Khwarizmi（780-850）的名字，他系统地整理了求解方程的方法。

一个算法必须具备以下性质：

输入：算法从指定的输入集合中获取输入值。输入可以是零个或多个。

输出：算法产生输出值，这些输出是问题的解。每个算法至少有一个输出。

正确性：对于每一组输入，算法都应产生正确的输出结果。

有限性：算法必须在有限步骤后终止，不能陷入无限循环。

确定性：算法的每一步都必须有明确的定义，不能有歧义。

有效性：算法的每一步都必须是可执行的，且能在有限时间内完成。

通用性：算法应能解决一类问题，而不仅仅是某个特定实例。

算法的描述方式

算法可以用多种方式描述：

自然语言：用日常语言描述算法步骤。优点是直观易懂，缺点是容易产生歧义。

伪代码：介于自然语言和编程语言之间的描述方式。忽略具体编程语言的语法细节，关注算法的核心逻辑。

流程图：用图形符号表示算法的执行流程。

编程语言：用具体的编程语言实现算法。

伪代码是最常用的算法描述方式，它具有以下特点：

• 使用结构化的控制结构（如 if-then-else、while、for）
• 不依赖特定编程语言的语法
• 易于转换为实际代码
• 便于分析算法的性质

算法示例：线性搜索

问题：在一个列表中查找特定元素的位置。

伪代码：

算法：线性搜索
输入：目标值 x，列表 [a₁, a₂, ..., aₙ]
输出：x 在列表中的位置（若找到）或 0（若未找到）

i := 1
while i ≤ n 且 x ≠ aᵢ do
    i := i + 1
if i ≤ n then
    返回 i
else
    返回 0

Python 实现：

def linear_search(arr, target):
    """线性搜索：在列表中查找目标元素"""
    for i in range(len(arr)):
        if arr[i] == target:
            return i + 1  # 返回位置（从1开始）
    return 0  # 未找到

# 示例
numbers = [3, 7, 1, 9, 4, 2]
print(linear_search(numbers, 9))   # 输出: 4
print(linear_search(numbers, 5))   # 输出: 0

线性搜索逐个检查列表中的元素，直到找到目标或遍历完整个列表。

算法示例：二分搜索

当列表已排序时，可以使用更高效的二分搜索算法。

伪代码：

算法：二分搜索
输入：目标值 x，已排序列表 [a₁, a₂, ..., aₙ]（递增）
输出：x 在列表中的位置（若找到）或 0（若未找到）

i := 1          // 搜索区间左端点
j := n          // 搜索区间右端点
while i < j do
    m := ⌊(i + j) / 2⌋
    if x > aₘ then
        i := m + 1
    else
        j := m
if x = aᵢ then
    返回 i
else
    返回 0

Python 实现：

def binary_search(arr, target):
    """二分搜索：在有序列表中查找目标元素"""
    left, right = 0, len(arr) - 1
    
    while left < right:
        mid = (left + right) // 2
        if target > arr[mid]:
            left = mid + 1
        else:
            right = mid
    
    if arr[left] == target:
        return left + 1  # 返回位置（从1开始）
    return 0

# 示例
sorted_numbers = [1, 2, 3, 4, 7, 9]
print(binary_search(sorted_numbers, 4))   # 输出: 4
print(binary_search(sorted_numbers, 5))   # 输出: 0

执行过程示例：在列表 [1, 2, 3, 5, 6, 7, 8, 10, 12, 13, 15, 16, 18, 19, 20, 22] 中查找 19。

1. 初始区间：位置 1-16，中点是位置 8（值 10）。19 > 10，搜索右半部分。
2. 区间：位置 9-16，中点是位置 12（值 16）。19 > 16，搜索右半部分。
3. 区间：位置 13-16，中点是位置 14（值 19）。19 = 19，继续缩小到位置 14。
4. 区间：位置 13-14，中点是位置 13（值 18）。19 > 18，搜索右半部分。
5. 区间缩小到位置 14，循环结束。arr[14] = 19，返回 14。

贪心算法

优化问题

优化问题是指在一组可能的解中找到最优解的问题。常见的优化问题包括：

• 在两个城市之间找到距离最短的路线
• 用最少的比特数编码信息
• 用最少的光纤连接网络节点

贪心算法（Greedy Algorithm）是解决优化问题的一种策略：在每一步选择当前看起来最优的选择，希望最终得到全局最优解。

贪心算法不一定总是能得到最优解，但在许多问题上确实有效。

贪心调度问题

问题：有一个会议室和多场讲座，每场讲座有开始时间和结束时间。如何安排尽可能多的讲座？

贪心策略选项：

1. 每次选择开始时间最早的讲座？不一定正确。
2. 每次选择持续时间最短的讲座？不一定正确。
3. 每次选择结束时间最早的讲座？这个策略是正确的！

为什么选择结束时间最早的讲座有效？

选择最早结束的讲座，给后续讲座留出最多的时间。这是一个可以严格证明的贪心策略。

算法伪代码：

算法：贪心调度
输入：n 场讲座的开始时间 s₁, ..., sₙ 和结束时间 e₁, ..., eₙ
输出：可安排的讲座集合 S

按结束时间排序讲座，使得 e₁ ≤ e₂ ≤ ... ≤ eₙ
S := 空集
for j := 1 to n do
    if 讲座 j 与 S 中的讲座不冲突 then
        S := S ∪ {j}
返回 S

Python 实现：

def greedy_scheduling(talks):
    """
    贪心调度算法
    talks: [(开始时间, 结束时间, 讲座名), ...]
    返回: 可安排的讲座列表
    """
    # 按结束时间排序
    sorted_talks = sorted(talks, key=lambda x: x[1])
    
    selected = []
    last_end = 0
    
    for start, end, name in sorted_talks:
        if start >= last_end:  # 不冲突
            selected.append((start, end, name))
            last_end = end
    
    return selected

# 示例
talks = [
    (1, 3, 'A'),
    (2, 5, 'B'),
    (4, 7, 'C'),
    (6, 9, 'D'),
    (8, 10, 'E'),
    (9, 11, 'F')
]

result = greedy_scheduling(talks)
for start, end, name in result:
    print(f"讲座 {name}: {start}-{end}")
# 输出: A(1-3), C(4-7), E(8-10)

正确性证明思路：

使用交换论证（Exchange Argument）。假设贪心解不是最优解，那么存在一个最优解在第一步没有选择最早结束的讲座。可以将最优解的第一个讲座替换为贪心选择（结束最早的讲座），这不会减少可安排的讲座数量，因为贪心选择结束更早。通过归纳，贪心解一定是最优的。

函数增长与渐近记号

函数增长的概念

分析算法效率时，我们关心的是当输入规模增大时，算法所需时间或空间如何增长。为此，我们需要比较函数的增长速度。

核心问题：当 $n$ 变得很大时，哪个函数增长得更快？

大 O 记号

大 O 记号描述函数增长的上界。

定义：设 $f, g: \mathbb{R} \to \mathbb{R}$。我们说 $f$ 是 $O(g)$（读作"f 是大 O of g"），如果存在正常数 $C$ 和 $k$，使得对于所有 $x > k$，有：

$|f(x)| \leq C|g(x)|$

常数 $C$ 和 $k$ 称为这一关系的见证（witness）。

直观理解：$f$ 是 $O(g)$ 意味着当 $x$ 足够大时，$f$ 的值不超过 $g$ 的某个常数倍。换句话说，$g$ 渐近地支配 $f$。

例子：证明 $f(x) = x^2 + 2x + 1$ 是 $O(x^2)$。

当 $x > 1$ 时：

• $x^2 + 2x + 1 \leq x^2 + 2x^2 + x^2 = 4x^2$

取 $k = 1$，$C = 4$，对于所有 $x > 1$，有 $|x^2 + 2x + 1| \leq 4|x^2|$。

因此 $x^2 + 2x + 1$ 是 $O(x^2)$。

常用记号说明：

虽然经常看到写作 $f(x) = O(g(x))$，但这不是严格意义的等式。更准确的说法是 $f \in O(g)$，因为 $O(g)$ 是满足条件的所有函数的集合。

多项式的增长

定理：如果 $f(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0$，其中 $a_n \neq 0$，则 $f(x)$ 是 $O(x^n)$。

证明：当 $x > 1$ 时： $|f(x)| \leq |a_n|x^n + |a_{n-1}|x^{n-1} + \cdots + |a_1|x + |a_0|$ $\leq |a_n|x^n + |a_{n-1}|x^n + \cdots + |a_1|x^n + |a_0|x^n$ $= (|a_n| + |a_{n-1}| + \cdots + |a_1| + |a_0|)x^n$

取 $C = |a_n| + |a_{n-1}| + \cdots + |a_0|$，$k = 1$，即得证。

这个定理告诉我们：多项式函数的增长速度由其最高次项决定。

常见函数的增长比较

按照增长速度从慢到快排列：

$1 < \log n < \sqrt{n} < n < n \log n < n^2 < n^3 < 2^n < n! < n^n$

重要性质：

• 如果 $d > c > 1$，则 $n^c$ 是 $O(n^d)$，但 $n^d$ 不是 $O(n^c)$
• 如果 $b > 1$ 且 $c > 0$，则 $(\log_b n)^c$ 是 $O(n^d)$，但 $n^d$ 不是 $O((\log_b n)^c)$
• 如果 $b > 1$ 且 $d > 0$，则 $n^d$ 是 $O(b^n)$，但 $b^n$ 不是 $O(n^d)$
• 如果 $c > b > 1$，则 $b^n$ 是 $O(c^n)$，但 $c^n$ 不是 $O(b^n)$

大 Omega 记号

大 Omega 记号描述函数增长的下界。

定义：设 $f, g: \mathbb{R} \to \mathbb{R}$。我们说 $f$ 是 $\Omega(g)$，如果存在正常数 $C$ 和 $k$，使得对于所有 $x > k$，有：

$|f(x)| \geq C|g(x)|$

直观理解：$f$ 是 $\Omega(g)$ 意味着当 $x$ 足够大时，$f$ 的值至少是 $g$ 的某个常数倍。

定理：$f$ 是 $\Omega(g)$ 当且仅当 $g$ 是 $O(f)$。

证明：根据定义，$f$ 是 $\Omega(g)$ 意味着存在 $C$ 和 $k$，使得 $|f(x)| \geq C|g(x)|$ 对所有 $x > k$ 成立。这等价于 $|g(x)| \leq \frac{1}{C}|f(x)|$，这正是 $g$ 是 $O(f)$ 的定义。

大 Theta 记号

大 Theta 记号描述函数增长的精确阶数。

定义：设 $f, g: \mathbb{R} \to \mathbb{R}$。我们说 $f$ 是 $\Theta(g)$，如果 $f$ 既是 $O(g)$ 又是 $\Omega(g)$。

等价定义：$f$ 是 $\Theta(g)$ 当且仅当存在正常数 $C_1$、$C_2$ 和 $k$，使得对于所有 $x > k$，有：

$C_1|g(x)| \leq |f(x)| \leq C_2|g(x)|$

直观理解：$f$ 是 $\Theta(g)$ 意味着 $f$ 和 $g$ 具有相同的增长阶数，它们渐近地以相同的速度增长。

例子：证明前 $n$ 个正整数之和 $1 + 2 + \cdots + n$ 是 $\Theta(n^2)$。

我们已经知道 $1 + 2 + \cdots + n = \frac{n(n+1)}{2} = \frac{n^2 + n}{2}$，这是 $O(n^2)$。

要证明也是 $\Omega(n^2)$：当 $n \geq 1$ 时： $1 + 2 + \cdots + n \geq \lceil n/2 \rceil + (\lceil n/2 \rceil + 1) + \cdots + n$ $\geq \lceil n/2 \rceil \cdot \lceil n/2 \rceil \geq \frac{n}{2} \cdot \frac{n}{2} = \frac{n^2}{4}$

取 $C_1 = \frac{1}{4}$，$C_2 = 1$，$k = 1$，即得证。

算法复杂度分析

时间复杂度

算法的时间复杂度是指算法运行所需的计算工作量。我们用基本操作（如比较、赋值、算术运算）的次数来衡量时间复杂度。

为什么关注最坏情况？

• 最坏情况给出了算法性能的上界保证
• 平均情况分析需要知道输入的概率分布，这在实践中往往难以确定
• 对于许多算法，最坏情况和平均情况的复杂度相同

线性搜索的复杂度分析

最坏情况：目标元素不在列表中，或位于列表末尾。

设列表有 $n$ 个元素。在每次循环中，进行 2 次比较（$i \leq n$ 和 $x \neq a_i$）。循环执行 $n$ 次后，还需要 1 次比较退出循环（$i \leq n$），以及循环后的 1 次比较（$i \leq n$）。

总比较次数：$2n + 1 + 1 = 2n + 2$

因此，线性搜索的最坏时间复杂度是 $O(n)$。

平均情况（假设目标元素在列表中，且出现在各位置的概率相等）：

如果目标在第 $i$ 个位置，比较次数为 $2i + 1$。

平均比较次数： $\frac{1}{n} \sum_{i=1}^{n} (2i + 1) = \frac{1}{n} \left(2 \cdot \frac{n(n+1)}{2} + n\right) = n + 2$

平均时间复杂度也是 $O(n)$。

二分搜索的复杂度分析

设列表有 $n$ 个元素，为简化分析，假设 $n = 2^k$。

每次迭代将搜索区间大小减半：

• 第一次迭代：区间大小为 $2^k$
• 第二次迭代：区间大小为 $2^{k-1}$
• ...
• 最后一次迭代：区间大小为 $2^0 = 1$

迭代次数为 $k = \log_2 n$。

每次迭代进行 2 次比较（$i < j$ 和 $x > a_m$），最后还有 2 次额外比较。

总比较次数：$2\log_2 n + 2$

因此，二分搜索的时间复杂度是 $O(\log n)$。

对比：对于 $n = 10^6$ 个元素：

• 线性搜索最多需要 $10^6$ 次比较
• 二分搜索最多需要约 $2 \times 20 + 2 = 42$ 次比较

二分搜索的效率显著高于线性搜索，但前提是列表必须已排序。

常见复杂度级别

复杂度	名称	典型算法
$O(1)$	常数时间	数组访问、哈希表查找
$O(\log n)$	对数时间	二分搜索、平衡树操作
$O(n)$	线性时间	线性搜索、遍历
$O(n \log n)$	线性对数时间	快速排序、归并排序
$O(n^2)$	平方时间	冒泡排序、选择排序
$O(n^3)$	立方时间	朴素矩阵乘法
$O(2^n)$	指数时间	子集枚举、回溯算法
$O(n!)$	阶乘时间	排列枚举、旅行商问题暴力求解

空间复杂度

空间复杂度衡量算法所需的存储空间。除了输入数据占用的空间外，算法还需要额外空间来存储中间结果、递归调用栈等。

例子：

• 迭代版本的线性搜索：空间复杂度 $O(1)$，只需常数额外空间
• 递归版本的线性搜索：空间复杂度 $O(n)$，递归深度最多为 $n$

在实际应用中，通常需要在时间效率和空间效率之间权衡。

算法正确性证明

循环不变式

循环不变式是证明算法正确性的重要工具。一个循环不变式是在循环的每次迭代前后都保持成立的性质。

循环不变式证明框架：

1. 初始化：证明在循环第一次迭代之前，循环不变式成立。
2. 保持性：证明如果循环不变式在迭代开始时成立，则在迭代结束时也成立。
3. 终止性：证明当循环终止时，循环不变式提供了证明算法正确性的性质。

证明线性搜索的正确性

循环不变式：在第 $i$ 次迭代开始时，目标元素 $x$ 不在 $a_1, a_2, \ldots, a_{i-1}$ 中。

初始化：$i = 1$ 时，前 0 个元素中不包含 $x$，平凡成立。

保持性：假设第 $i$ 次迭代开始时，$x$ 不在 $a_1, \ldots, a_{i-1}$ 中。

• 如果 $x = a_i$，则找到目标，循环结束，返回正确位置 $i$。
• 如果 $x \neq a_i$，则 $x$ 不在 $a_1, \ldots, a_i$ 中，迭代后 $i$ 增加，循环不变式对下一次迭代成立。

终止性：循环在 $i > n$ 或 $x = a_i$ 时终止。

• 如果 $x = a_i$，返回正确位置。
• 如果 $i > n$，说明 $x$ 不在列表中，返回 0 是正确的。

证明二分搜索的正确性

循环不变式：每次迭代开始时，如果目标 $x$ 在列表中，则它一定在区间 $[i, j]$ 内。

初始化：$i = 1$，$j = n$，区间包含整个列表，不变式成立。

保持性：设 $m = \lfloor (i+j)/2 \rfloor$。

• 如果 $x > a_m$，则 $x$ 只可能在 $[m+1, j]$ 中（因为列表递增），新的区间为 $[m+1, j]$。
• 如果 $x \leq a_m$，则 $x$ 只可能在 $[i, m]$ 中，新的区间为 $[i, m]$。

无论哪种情况，如果 $x$ 在原区间中，则它一定在新区间中。

终止性：当 $i \geq j$ 时循环终止，此时区间大小为 1。

• 如果 $x = a_i$，返回 $i$，正确。
• 如果 $x \neq a_i$，则 $x$ 不在列表中，返回 0，正确。

算法设计范式

分治法

分治法（Divide and Conquer）将问题分解为多个相似的子问题，递归求解子问题，然后合并结果。

基本步骤：

1. 分解：将原问题分解为若干规模较小的子问题
2. 解决：递归求解各子问题
3. 合并：将子问题的解合并为原问题的解

例子：归并排序

def merge_sort(arr):
    """归并排序"""
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    return merge(left, right)

def merge(left, right):
    """合并两个有序列表"""
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    return result

# 示例
arr = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(arr))  # [3, 9, 10, 27, 38, 43, 82]

时间复杂度分析：

设 $T(n)$ 为排序 $n$ 个元素的时间： $T(n) = 2T(n/2) + O(n)$

使用主定理，$T(n) = O(n \log n)$。

动态规划

动态规划（Dynamic Programming）适用于有重叠子问题和最优子结构的问题。

核心思想：将问题分解为子问题，存储子问题的解，避免重复计算。

例子：斐波那契数列

朴素递归的时间复杂度是 $O(2^n)$，使用动态规划可优化到 $O(n)$。

def fibonacci_dp(n):
    """动态规划求斐波那契数"""
    if n <= 1:
        return n
    
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1
    
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]

# 空间优化版本
def fibonacci_optimized(n):
    """空间优化的斐波那契数"""
    if n <= 1:
        return n
    
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    
    return curr

print(fibonacci_optimized(10))  # 55

小结

本章介绍了算法的基础知识：

1. 算法的概念：定义、性质、描述方式
2. 搜索算法：线性搜索和二分搜索
3. 贪心算法：贪心策略及其应用
4. 渐近记号：大 O、大 Omega、大 Theta 记号
5. 复杂度分析：时间复杂度、空间复杂度
6. 正确性证明：循环不变式方法
7. 算法设计范式：分治法、动态规划

算法是计算机科学的灵魂。掌握算法的分析和设计方法，是成为优秀程序员的基础。本章从离散数学的角度建立了算法分析的数学基础，为进一步学习算法课程做好准备。

练习

1. 用伪代码描述一个算法，找出列表中的最大元素。

2. 证明：$f(n) = 3n^2 + 5n - 2$ 是 $\Theta(n^2)$。

3. 分析以下代码的时间复杂度：

   for i in range(n):
       for j in range(i, n):
           print(i, j)

4. 使用循环不变式证明二分搜索的正确性。

5. 设计一个贪心算法解决找零问题：给定硬币面值 1, 5, 10, 25，用最少的硬币凑出金额 $n$。分析算法是否总是得到最优解。