Meet in middle 算法记录

__vector__ · 2022-07-20 21:15:02 · 个人记录

原理

假设有 n 个节点，而为了搜一个解需要遍历这 n 个点。

如果复杂度较低，如遍历的复杂度为 O(n)，倒没有必要用这个算法。

但是如果复杂度很高，如 O(n^2)，而 n \le 20000；或者 O(2^n)，n \le 40 等，就很有用了。

这个算法是分别从两端开始搜，两端分别搜索 \frac{n}{2} 个节点，最后再把两端搜索到的结果拼接起来。

原来的 O(n^2) 复杂度虽然还是 O(n^2)，但是由于 n 除了 2，效率提升很大。

而 O(2^n) \rightarrow O(2^\frac{n}{2})，效率提升巨大。