算法分析与复杂度类

算法分析用于确定算法的资源需求如何随输入增长。在实现细节、硬件和具有代表性的工作负载掩盖主要成本之前，它可以支持设计决策。有效的分析需要确定输入规模，明确资源，并在推导界限之前说明成本模型。

定义成本 #

选择能够表示输入的规模参数。数组算法通常使用 \(n\)，而图算法则需要同时考虑顶点 \(V\) 和边 \(E\)。还要明确资源类型：比较次数、内存消耗、磁盘 I/O、网络往返次数，或在已定义机器模型下的耗时。

RAM 模型将对字长值执行的算术运算、比较、索引和指针操作视为常数时间操作。该假设使 RAM 模型适用于内存中的算法；而外部存储算法必须计算块传输次数，因为随机磁盘访问并不具有常数成本。

渐近记法 #

渐近记法比较输入增长时的非负成本函数。由于常数因子和低阶项不会改变增长类，因此将其省略。

当存在常数 \(c > 0\) 和 \(n_0\)，使得对于每个 \(n \geq n_0\)，都有 \(f(n) \leq c g(n)\) 时，\(f(n) \in O(g(n))\)。Big O 给出渐近上界。
当 \(g(n) \in O(f(n))\) 时，\(f(n) \in \Omega(g(n))\)。Big Omega 给出渐近下界。
当上述两个关系都成立时，\(f(n) \in \Theta(g(n))\)。Big Theta 给出渐近紧确界。

例如，\(3n^2 + 10n + 4\) 属于 \(\Theta(n^2)\)。在已排序数组中，二分搜索进行 \(O(\log n)\) 次比较；而使用邻接表表示的图进行广度优先搜索需要 \(\Theta(V + E)\) 时间。不注明所测量的资源，复杂度界限可能会产生误导：基于比较的排序可以使用 \(O(n \log n)\) 次比较，但仍然需要 \(O(n)\) 的辅助内存。

分析迭代算法 #

计算每个循环执行的工作量，并将所有迭代的工作量相加。连续循环的成本相加；只有当一个循环的每次迭代都会执行另一个循环的全部迭代时，嵌套循环的成本才相乘。

cpp

#include <cstddef>
#include <vector>

std::size_t lower_bound_index(const std::vector<int>& values, int target) {
    std::size_t first = 0;
    std::size_t last = values.size();

    while (first < last) {
        const std::size_t middle = first + (last - first) / 2;
        if (values[middle] < target) {
            first = middle + 1;
        } else {
            last = middle;
        }
    }
    return first;
}

每次迭代都会使搜索区间至少减半。因此，其运行时间为 \(O(\log n)\)，而迭代实现使用 \(O(1)\) 的辅助空间。依赖于前一个循环变量的循环边界需要使用求和来分析；例如，\(\sum_{i=1}^{n} i = \Theta(n^2)\)。

递推式与分治 #

递归算法通常会产生递推式。归并排序将输入划分为两个部分，并执行线性时间的合并，因此得到：

\[ T(n) = 2T(n / 2) + \Theta(n) \]

递归具有 \(\log_2 n\) 个层级，每个层级执行 \(\Theta(n)\) 的工作。因此，归并排序的运行时间为 \(\Theta(n \log n)\)。递归树可以直接展示这种结构。对于形如 \(T(n) = aT(n / b) + f(n)\) 的递推式，主定理通过比较 \(f(n)\) 与 \(n^{\log_b a}\) 来分类结果；当前提条件不适用时，应使用递归树或代入法证明。

最坏情况、期望成本与摊销成本 #

最坏情况分析对给定规模的每个输入进行界定。即使最坏输入很少出现，它仍然能够提供可靠的容量上限。平均情况分析需要明确的输入分布；如果不存在这样的分布，将某个界限称为“平均”并没有数学意义。

期望分析用于随机化算法。当枢轴选择避免了对抗性顺序时，随机化快速排序的期望运行时间为 \(\Theta(n \log n)\)，尽管某次具体执行可能需要 \(\Theta(n^2)\) 时间。

摊销分析不假设输入分布，而是对一系列操作进行界定。向按几何方式增长的 std::vector 追加元素时，偶尔会重新分配并复制 \(\Theta(n)\) 个元素，但每个元素只会被复制有限次。因此，一系列追加操作的总成本对应于每次追加 \(O(1)\) 的摊销时间。聚合方法、记账法和势能法是证明此类界限的等价方法。

判定问题与 NP 完全性 #

判定问题的答案是 yes 或 no。复杂度类定义在判定问题上，因为多项式时间归约会保留这些答案。

当确定性机器能够在多项式时间内判定某个语言时，该语言属于 P。当每个 yes 实例都具有一个能够由确定性机器在多项式时间内验证的证书时，该语言属于 NP。因此，\(P \subseteq NP\)。

如果 NP 中的每个问题都能在多项式时间内归约到某个问题，则该问题是 NP 困难的。如果一个问题同时是 NP 困难的并且属于 NP，则它是 NP 完全的。NP 完全性证明需要：

一个用于证明问题属于 NP 的多项式时间验证器；以及
从已知 NP 完全问题出发的多项式时间归约。

\(P = NP\) 是否成立仍然是一个开放问题。NP 完全性并不意味着实际实例无法求解；问题结构、参数界限、近似算法和启发式方法都可能使特定实例变得可处理。