Skip to content

05_Algorithms

一、 算法基础 (Algorithms)

  • 定义: 算法是执行计算或解决问题的有限指令集，能够将合法输入转换为预期输出。

  • 六大特征:

    1. 输入 (Input): 具有特定集合的输入值。

    2. 输出 (Output): 产生特定集合的输出值。

    3. 正确性 (Correctness): 对任何合法输入均能产生正确输出。

    4. 有限性 (Finiteness): 必须在有限步内终止并输出。

    5. 有效性 (Effectiveness): 每一步都必须能在有限时间内精确执行。

    6. 通用性 (Generality): 能够解决该形式的所有问题，而不仅仅是特定测试用例。

问题分类与算法

  • 三大问题领域: 搜索问题 (找寻元素位置)、排序问题 (按序排列元素)、优化问题 (求最大或最小值)。

  • 贪心算法 (Greedy Algorithms): 在每一步做出局部最优解，期望由此达到全局最优。但贪心算法不能保证必然得出最优解，必须经过数学证明或寻找反例来验证。

  • 停机问题 (The Halting Problem): 不可解 (Unsolvable)。

    • 反证法核心: 假设存在能判断程序是否停机的通用程序 \(H(P, I)\)，构造一个恶意程序 \(K(P)\) 使其行为与 \(H\) 的判断完全相反。当运行 \(K(K)\) 时，若 \(H\) 预测停机，\(K\) 则死循环；若 \(H\) 预测死循环，\(K\) 则停机。得出悖论，证明 \(H\) 不存在。

二、 函数的增长与渐进符号 (Growth of Functions)

1. 渐进符号定义

  • 大O符号 (\(O\)) - 渐进上限:

    • 存在常数 \(C\) 和 \(k\)（称为见证人 Witnesses），使得当 \(x > k\) 时，\(|f(x)| \le C|g(x)|\)，记作 \(f(x)\) 是 \(O(g(x))\)。

  • 大\(\Omega\)符号 (\(\Omega\)) - 渐进下限:

    • 存在常数 \(C\) 和 \(k\)，使得当 \(x > k\) 时，\(|f(x)| \ge C|g(x)|\)。

    • \(f(x)\) 是 \(\Omega(g(x))\) 当且仅当 \(g(x)\) 是 \(O(f(x))\)。

  • 大\(\Theta\)符号 (\(\Theta\)) - 紧确界:

    • 若 \(f(x)\) 既是 \(O(g(x))\) 又是 \(\Omega(g(x))\)，则 \(f(x)\) 是 \(\Theta(g(x))\)。表示两者增长阶数相同。

2. 常见函数的估计与法则

  • 多项式: 由最高次项主导。若 \(f(x) = a_nx^n + \dots + a_0\)，则 \(f(x)\) 是 \(\Theta(x^n)\)。

  • 前 \(n\) 个正整数之和: 是 \(O(n^2)\) 以及 \(\Theta(n^2)\)。

  • 阶乘与对数: \(n!\) 是 \(O(n^n)\)；\(\log(n!)\) 是 \(O(n \log n)\)。

  • 运算法则:

    • 加法法则: 若 \(f_1 = O(g_1)\) 且 \(f_2 = O(g_2)\)，则 \(f_1 + f_2\) 是 \(O(\max(|g_1|, |g_2|))\)。

    • 乘法法则: \(f_1 f_2\) 是 \(O(g_1 g_2)\)。

3. 函数增长阶数排序 (从慢到快)

常数 (\(1\)) < 双重对数 (\(\log(\log n)\)) < 对数多项式 (\((\log n)^2\)) < 混合多项式 (\(n^2(\log n)^3\)) < 多项式 (\(n^3\)) < 小底数指数 (\((1.5)^n\)) < 大底数指数 (\(2^n\)) < 指数混合 (\(2^n(n^2+1)\)) < 阶乘 (\(n!\))。

三、 算法复杂度分析 (Complexity of Algorithms)

1. 核心指标

  • 时间复杂度: 解决问题所需的基本操作次数（如比较、加法、乘法）。

  • 分析原则: 忽略硬件、系统平台和具体数据结构等实现细节，重点使用大 \(O\) 和大 \(\Theta\) 评估。

  • 最坏情况 vs 平均情况: 重点关注最坏情况时间复杂度（提供操作数的上限）；平均情况通常难以数学计算。

2. 常见算法的时间复杂度

  • 查找算法:

    • 寻找最大值: \(2n-1\) 次比较，\(\Theta(n)\)。

    • 线性查找 (Linear Search): 最坏 \(\Theta(n)\)，平均 \(\Theta(n)\)。

    • 二分查找 (Binary Search): 每次区间折半，最坏比较 \(2\log n + 2\) 次，\(\Theta(\log n)\)。

  • 排序算法:

    • 冒泡排序 (Bubble Sort) & 插入排序 (Insertion Sort): 均需 \(\frac{n(n-1)}{2}\) 级别次比较，最坏复杂度皆为 \(\Theta(n^2)\)。

  • 矩阵操作:

    • 标准矩阵乘法: 需 \(n^3\) 次乘法和 \(n^2(n-1)\) 次加法，\(O(n^3)\)。

    • 布尔乘积: \(O(n^3)\)。

    • 矩阵链乘法 (优化): 乘法顺序极大影响运算量，通常使用动态规划 (Dynamic Programming) 优化。

3. 算法范式与术语

  • 暴力法 (Brute-Force): 最直接、不加优化技巧的解法（如线性查找、冒泡排序）。

  • 标准复杂度术语: \(\Theta(1)\) 常数，\(\Theta(\log n)\) 对数，\(\Theta(n)\) 线性，\(\Theta(n \log n)\) 线性对数，\(\Theta(n^b)\) 多项式，\(\Theta(b^n)\) 指数，\(\Theta(n!)\) 阶乘。

四、 复杂性类别与 P vs NP (P vs NP Problem)

问题本身根据是否存在解题算法进行分类：

  • 易解的 (Tractable): 存在多项式时间的算法，属于 P 类 (Class P)。

  • 难解的 (Intractable): 不存在多项式时间的算法。

  • 不可解的 (Unsolvable): 完全不存在求解算法（如停机问题）。

  • NP 类 (Nondeterministic Polynomial): 给出一个候选解，能够在多项式时间内验证其正确性，但尚未找到能在多项式时间内求解的算法。

  • NP 完全问题 (NP-Complete): NP 类的一个特定子集。如果能够找到任意一个 NP 完全问题的多项式时间算法，就能将其转化为解决所有 NP 问题的多项式时间算法。

  • P vs NP 问题: 理论计算机科学中最著名的未解之谜。核心疑问是“那些可以快速验证解的问题，是否也能快速求出解？”。目前普遍认为 \(P \neq NP\)，但尚未得到数学证明。