算法优化技术

输入增强先分析输入并保存额外信息，让后续步骤不再重复劳动。KMP 的前缀表、Horspool 的字符位置表以及计数排序的计数数组都属于这一类。

若关键字是 \([0,k]\) 内的整数，计数排序先统计频数，再作前缀和确定每个值在输出中的结束位置。为保持稳定，应从右向左扫描原数组：

for i = n-1 downto 0:
    B[C[A[i]] - 1] = A[i]
    C[A[i]]--

时间 \(O(n+k)\)，空间 \(O(n+k)\)。当 \(k\) 远大于 \(n\) 时，计数数组并不经济。它能突破比较排序下界，是因为利用了关键字取值范围，而不是只作比较。

预构造则提前建立更适合访问的数据结构。二叉搜索树、倒排索引、并查集和堆分别为动态查找、复合查询、集合合并和优先级访问准备了结构。预处理只有在后续收益超过建表和维护成本时才值得做。

预先计算函数表，可以把重复求函数值降到 \(O(1)\) 查询；一个字节只有 \(256\) 种状态，也可以预存全部比特逆序结果。散列表、缓存和动态规划表都是典型的“用空间换时间”。

反过来，内存受限时可以接受重复计算或采用滚动数组、原地更新。这里没有固定方向，关键是同时估计：预处理时间、额外空间、查询次数、更新频率以及缓存局部性。

不同方法往往擅长不同阶段。快速排序在大区间上效率高，小区间却要付出递归和划分开销；可在区间小于阈值时停止递归，最后对整个近乎有序的数组作一次插入排序。

非线性求根中，二分稳定但慢，Newton、割线或反插值快却依赖初值。维持一个异号包围区间，快速步越界或进展不够时退回二分，就能同时保留安全性和局部快速收敛。优化不是把某个局部技巧无限使用，而是让方法在各自合适的阶段接力。

评论