为什么弗洛伊德周期检测算法假设在与野兔相遇之前最多绕周期一圈?为什么它不能跑多圈? 直观和正式的解释将不胜感激。
我想我可以提供一个直观的解释。
我们可以有两种情况:要么有循环,要么没有。
如果没有周期:hare
将在tortoise
之前到达列表的末尾,所以我们完成了。
如果有周期:
它的长度必须n
,我们记得hare
的"速度"是tortoise's
的两倍。
一旦tortoise
进入循环,hare
就会在循环中的某个地方(可能已经绕了几次)。无论如何,它是tortoise
后面的x
节点(记住x <= n-1
因为如果它们在同一个节点上,我们将在这里结束)。
由于hare
的"速度"是tortoise
的两倍,它将在x
"步"内"追上"它。
QED。