algorithm - 布伦特周期检测算法

Question

谁能帮我解决布伦特周期检测算法。我不明白为什么“搜索大于 λ 和 μ 的两个 2^i 的最小幂”？ 2 的幂如何在循环检测中发挥作用。它与弗洛伊德的循环检测算法有某种关系吗？我无法从基础知识中得到它。请帮忙 !

Answer 1

此方法使用递增步骤(1、2、4、8 ...)尽快进入循环。当 P = 2^k 变得大于 λ 和 μ 时，乌龟 (T) 就在循环中，而兔子 (H) 只走 P 步就可以再次遇到(站立的)乌龟。似乎一些模拟会很有用。让我们有列表 0-1-2-3-4-5-6-7-3

P=1 T=0 H=0; H makes 1 step and doesn't meet T
P=2 T=1 H=1; H makes 2 steps and doesn't meet T
P=4 T=3 H=3; H makes 4 steps and doesn't meet T 
P=8 T=7 H=7; H makes 5 steps and meets T !!!!!

注意:当 P=4 时，T 在循环内，但 hare 不会完成整个循环(P >= μ 但 P < λ )

因此我们发现 μ<8 且 λ=5。然后我们要找到μ(循环入口点)

T=0 H=0; H makes 5 steps; H=5 
while T <> H 
   move both
T=1 H=6
T=2 H=7
T=3 H=3 !!!!!!!

我们刚找到 μ=3