第 3 章算法¶

章节导引

本页从《离散数学讲义》拆分而来，保留原章节锚点，方便从旧总览页和旧链接跳转。

学习目标¶

把问题描述成算法步骤，并能用渐近记号比较算法规模增长。

前置知识¶

第 2 章的函数和序列，基础程序流程，以及对循环/递归的直观理解。

建议用时¶

建议 3–4 小时：算法表达 1 小时，搜索排序 1 小时，复杂度比较 1–2 小时。

练习建议¶

为搜索或排序写一段伪代码；估算 3 段循环的 Big-O；比较两组函数增长顺序。

参考资料与引用边界¶

整理者：Lumner。
课程来源：根据 DM/ 目录下的课件整理；本章对应课件：DM3.1-3.3(4).pdf。
原始讲义文件：note/离散数学讲义.md。
引用边界：这是公开学习笔记，不替代课程正式教材、教师课件或考试要求；外部引用时请注明来自本网站整理版。

3.0 核心目标¶

算法章节关注三个问题：

如何精确定义一个算法。
如何描述常见算法范式。
如何分析算法效率，尤其是时间复杂度。

3.1 算法¶

算法定义¶

算法是用于执行计算或解决问题的一组有限、精确指令。

算法应满足：

性质	含义
输入	从指定集合获得输入值
输出	产生问题所需的输出
确定性	每一步必须清楚明确
正确性	对合法输入产生正确输出
有限性	对任意合法输入都在有限步后停止
有效性	每一步都能实际执行
通用性	能处理一类问题，而非单个样例

伪代码¶

伪代码介于自然语言和程序语言之间，用于清晰描述算法而不依赖具体语言。

求有限整数序列最大值：

procedure max(a1, a2, ..., an: integers)
    max := a1
    for i := 2 to n
        if max < ai then max := ai
    return max

搜索问题¶

一般搜索问题：给定列表 \(a_1,a_2,\ldots,a_n\) 和目标 \(x\)，找出 \(x\) 在列表中的位置；若不存在则返回 0 或其他失败标记。

线性搜索：

procedure linear_search(x, a1, a2, ..., an)
    i := 1
    while i <= n and x != ai
        i := i + 1
    if i <= n then location := i
    else location := 0
    return location

适用于无序列表，最坏情况下要检查 \(n\) 个元素。

二分搜索适用于递增有序列表：

procedure binary_search(x, a1, a2, ..., an)
    i := 1
    j := n
    while i < j
        m := floor((i + j) / 2)
        if x > am then i := m + 1
        else j := m
    if x = ai then location := i
    else location := 0
    return location

每次将搜索区间约减为约一半，效率远高于线性搜索。

排序问题¶

排序是把列表元素按升序、字典序等规则排列。排序重要，因为大量计算任务依赖有序数据，例如搜索、数据库索引和数据展示。

课件当前主要提到排序问题本身，具体排序算法可在后续补充。

贪心算法¶

贪心算法每一步都选择当前看起来最优的局部选择。它不一定总能得到全局最优，但在某些问题上可以证明正确。

找零问题：对于美国硬币面值 25、10、5、1 美分，贪心策略每次选择不超过剩余金额的最大硬币。该策略能得到最少硬币数。

证明贪心正确通常需要：

找出最优解的结构性质。
证明存在一个最优解包含贪心第一步选择。
把问题缩小为子问题。

3.2 函数增长¶

为什么关心增长率¶

算法实际运行时间不仅取决于机器速度，也取决于输入规模。增长率描述输入变大时，运行时间如何变化。

例如：

\(30n+8\) 在小规模时可能比 \(n^2+1\) 大，但当 \(n\) 足够大时，二次函数会超过线性函数。

Big-O¶

设 \(f,g\) 是从整数或实数到实数的函数。若存在常数 \(C>0\) 和 \(k\)，使得当 \(x>k\) 时：

\(|f(x)|\le C|g(x)|\)

则称 \(f(x)\) 是 \(O(g(x))\)。

Big-O 给出渐近上界。

例：\(x^2+2x+1\) 是 \(O(x^2)\)。

当 \(x>1\) 时：

\(x^2+2x+1\le x^2+2x^2+x^2=4x^2\)

可取 \(C=4,k=1\)。

多项式增长¶

若：

\(f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0\)

且 \(a_n\ne0\)，则：

\(f(x)=O(x^n)\)

事实上 \(f(x)=\Theta(x^n)\)。

常见增长顺序¶

从慢到快大致为：

\(1,\ \log n,\ n,\ n\log n,\ n^2,\ n^3,\ 2^n,\ n!\)

重要关系：

任意正幂的对数都比任意正幂的多项式慢。
任意固定次数多项式都比指数函数慢。
指数函数通常比阶乘慢。

Big-Omega 和 Big-Theta¶

若存在 \(C>0,k\)，当 \(x>k\) 时：

\(|f(x)|\ge C|g(x)|\)

则 \(f(x)=\Omega(g(x))\)。Big-Omega 给出渐近下界。

若：

\(f(x)=O(g(x))\) 且 \(f(x)=\Omega(g(x))\)

则：

\(f(x)=\Theta(g(x))\)

Big-Theta 表示同阶增长。

例：\(3x^2+8x\log x=\Theta(x^2)\)，因为 \(x\log x=O(x^2)\)，且主导项为 \(x^2\)。

组合函数的增长¶

若 \(f_1=O(g_1)\) 且 \(f_2=O(g_2)\)，则：

\(f_1+f_2=O(\max(g_1,g_2))\)

\(f_1f_2=O(g_1g_2)\)

例：\(n^2+\log(n!)\)。

由于 \(\log(n!)=O(n\log n)\)，所以整体为 \(O(n^2)\)，因为 \(n\log n=O(n^2)\)。

3.3 算法复杂度¶

时间复杂度¶

时间复杂度估计算法所需基本操作次数随输入规模增长的情况。本课程主要关注时间复杂度。

类型：

最坏情况复杂度：所有输入中最多需要多少操作。
最好情况复杂度：最有利输入下需要多少操作。
平均情况复杂度：按某种输入分布的平均操作次数。

最大值算法复杂度¶

求 \(n\) 个数最大值需要比较 \(n-1\) 次，因此时间复杂度为：

\(\Theta(n)\)

线性搜索复杂度¶

最坏情况：目标在最后一个位置或不存在，需要 \(n\) 次比较，所以为：

\(\Theta(n)\)

若目标一定在列表中且位置等可能，则平均比较次数：

\(\frac{1+2+\cdots+n}{n}=\frac{n+1}{2}\)

仍为 \(\Theta(n)\)。

二分搜索复杂度¶

每次比较后，候选区间约减半。最坏情况下比较次数约为：

\(\lceil\log_2 n\rceil+1\)

所以二分搜索为：

\(\Theta(\log n)\)

可处理、不可处理、不可解¶

课件提到算法问题的更高层次分类：

tractable：通常指多项式时间可解。
intractable：可能可解，但没有已知高效算法。
unsolvable：不存在算法能解决所有实例。
P 与 NP：计算复杂性理论的核心问题。

这些内容当前只作引入，后续若有复杂性理论课件可继续补充。

本章小结与后续扩展¶

本章已覆盖算法定义、搜索、贪心、渐近记号和复杂度分析。后续可补充：

常见排序算法。
图算法中的 BFS、DFS、最短路。
贪心算法正确性证明模板。
P、NP、NP-complete 基础。

第 3 章 算法¶