关于算法的一些思考

作为一个acm仔，我又回来写算法文章了，已经快一年没碰算法的我，在最近的简单算法复习中突然有了新的思考。记得在大一大二的时候，都是机械化的为了比赛刷题，背板子。或许不知道从什么时候开始，早就已经没有了最开始的热爱。废话不说，谈谈对最近对算法的一些理解吧。我认为算法本质就是信息复用。

“利用每次运算的额外信息减少重复劳动”，这正是很多高效算法的核心逻辑。无论是二分查找的 “范围收缩”，还是马拉车算法的 “对称复用”，本质上都是通过对 “已有信息” 的最大化利用，避免无效的重复计算，从而实现效率的跃升。我们可以结合具体例子，更细致地拆解这种 “信息复用” 的逻辑：

一、二分查找：用 “比较结果” 切割问题边界，排除无效范围

二分查找的优化逻辑，完美诠释了 “用信息减少重复劳动”。对于一个有序数组，暴力查找需要逐个比较（O (n)），本质是因为每次比较只能确定 “当前元素是否为目标”，没有产生额外信息；而二分查找的每一步，都能通过一次比较得到 “目标所在的范围”，从而直接排除一半元素。

具体来说：

1. 初始范围是整个数组（left=0，right=n-1），取中点 mid 比较 nums[mid] 与目标值；
2. 若 nums[mid] > 目标：说明目标只可能在左半段（right=mid-1），右半段可直接排除；
3. 若 nums[mid] < 目标：说明目标只可能在右半段（left=mid+1），左半段可直接排除；
4. 重复上述步骤，每次比较都将问题规模缩小一半（从 n 到 n/2，再到 n/4...），最终复杂度降至 O (log n)。

这里的 “额外信息” 是 **“目标与中点的大小关系”**，它直接决定了 “哪些元素不可能是目标”，从而避免了对这部分元素的重复比较。这种 “用信息切割范围” 的思路，在很多算法中都有体现（如快速排序的 partition 操作，用基准值切割数组为 “小于” 和 “大于” 两部分）。

二、马拉车算法（Manacher）：用 “回文对称性” 复用已有计算结果

最长回文子串问题中，暴力解法需要枚举所有可能的中心并向两边扩展（O (n²)），但很多情况下，右边的回文子串可以通过左边已计算的结果直接推导 —— 这正是马拉车算法的核心，它利用 “回文的对称性” 存储额外信息，减少重复扩展。

具体来说：

1. 马拉车算法通过记录 “当前已知的最长回文右边界 R” 和 “对应的中心 C”；
2. 当处理新位置 i 时，若 i < R（即 i 在当前回文范围内），则 i 关于 C 的对称点 j = 2C - i；
3. 此时，i 处的回文长度至少与 j 处相同（对称特性），无需从头扩展，只需从 “已知的最小长度” 开始继续向外比较；
4. 若扩展后超过 R，则更新 C 和 R，为后续位置提供新的 “对称信息”。

这里的 “额外信息” 是 **“之前回文的对称范围和长度”**，它让右边的计算不必从零开始，而是基于左边的结果 “站在巨人的肩膀上”，最终将复杂度从 O (n²) 优化到 O (n)。

三、其他算法中的 “信息复用” 逻辑

这种 “用额外信息减少重复劳动” 的思路，几乎贯穿了所有高效算法：

• 动态规划（DP）：通过存储 “子问题的解”（如斐波那契数列的dp[i]），避免对同一子问题的多次计算，用空间换时间；
• KMP 算法：通过前缀函数next数组记录 “模式串中已匹配的前缀信息”，当匹配失败时，无需从头比较，而是根据next跳转到最近的有效位置，减少无效匹配；
• 并查集（Union-Find）：通过 “路径压缩” 和 “按秩合并” 记录 “节点的父节点关系”，让每次查询和合并操作的复杂度接近 O (1)，避免了对整个树的重复遍历；
• 滑动窗口：用左右指针维护 “当前有效窗口”，通过窗口内元素的增减动态更新结果（如最长无重复子串），避免对窗口外元素的重复检查。

总结：算法优化的核心 ——“让每一步都不白走”

从本质上看，算法的优化过程，就是对 “信息” 的挖掘和利用过程：

• 低效算法的问题在于 “每一步只解决当前问题，不产生可复用的信息”（如暴力遍历）；
• 高效算法的关键在于 “让每一步运算都产生‘对后续步骤有用的信息’”，从而让后续步骤可以 “少走弯路”。

这种思路也适用于工程实践：比如缓存（Cache）的设计，本质是通过存储 “最近访问的数据”（额外信息），减少对底层存储的重复读取；再比如数据库索引，通过存储 “数据的位置映射”（额外信息），避免全表扫描。

理解了这一点，我们在设计或学习算法时，就可以多问自己：“这一步运算能产生什么可复用的信息？如何让后续步骤利用这些信息？”—— 这往往是突破算法瓶颈的关键。