布伦特的循环检测算法

Question

任何人都可以帮我解决布伦特的循环检测算法.我不明白为什么"寻找比λ和μ都大的两个2 ^ i的最小功率"？2的权力如何在循环的检测中发挥作用.它是否与Floyd的循环检测算法有某种关系？我无法从基础知识中获得它.请帮忙 !

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在循环内部时,但野兔不会经历整个循环(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