学习心得 - 数学 - meet in the middle 模型

· · 算法·理论

折半搜索

字面意思，从起点和终点同时搜，在中间碰面，复杂度可以由 2^n 降为 2\times2^{\frac{n}{2}}。

生日悖论

一个 n=10^9 点的随机图，要从 s 走到 t，此时从 s、t 各访问 \sqrt{n} 个点，有很大几率有点相同。