在乌龟和野兔算法中，为什么我们将野兔向前推进2步并进行检查

Question

在乌龟和野兔算法中，为什么总是让兔子前进两步，然后向前前进1步，然后将它们进行比较，我们也可以使兔子前进1步，然后再次检查其是否相等，然后再增加乌龟和野兔检查它们是否相等！我认为这将有助于更快地找到循环？

例如。这个伪指令

tortoise := firstNode
hare := firstNode

forever:

  if hare == end 
    return 'No Loop Found'

  hare := hare.next

  if hare == end
    return 'No Loop Found'
   if hare==tortoise
return true

  hare = hare.next
  tortoise = tortoise.next

  if hare == tortoise
    return 'Loop Found'

提前致谢

Answer 1

路径由尾部和循环组成；野兔和乌龟都要经过尾巴才能到达回路。由于野兔一次移动了两步，所以它首先进入循环，并在循环中运行直到乌龟到来。直到乌龟到达回路为止，他们两个不可能占据同一个牢房。

一旦乌龟到达循环的起点，兔子就在循环中的某个地方，有效地k步入了乌龟后面一定的k地方，k这肯定小于循环的大小。乌龟每走一步，野兔就走两步，这使野兔离乌龟更近了一步。因此，在乌龟移动了一步之后，它们之间的距离为k-1，然后是下一步k-2，依此类推，直到野兔一步步追上了k。

野兔决不会在回路中经过乌龟，因此没有必要检查野兔越过的地方。它不可能在那里。因此，额外的检查将始终失败，并且包括该检查只会减慢算法速度。