algorithm - 为什么在链表中查找循环时将指针增加 2，为什么不增加 3、4、5？

Question

我看过question已经讨论了在链表中查找循环的算法。我读过Floyd's cycle-finding algorithm解决方案，在很多地方都提到我们必须采取两个指针。一个指针(slower/tortoise)增加 1，另一个指针(faster/hare)增加 2。当它们相等时，我们找到循环，如果 faster 指针到达 null，则链表中没有循环。

现在我的问题是为什么我们将 faster pointer 增加 2。为什么不是别的？增加 2 是必要的，或者我们可以将其增加 X 以获得结果。如果我们将 faster pointer 递增 2 是否有必要找到一个循环，或者可能存在我们需要递增 3 或 5 或 x 的情况。

Answer 1

从正确性的角度来看，没有理由需要使用数字二。任何步长大小的选择都可以(当然除了一个)。但是，选择大小为 2 的步长可以最大限度地提高效率。

要了解这一点，让我们首先了解一下弗洛伊德算法为何有效。这个想法是考虑序列 x₀, x₁, x₂, ..., x_n, ... 如果您从列表的开头开始，然后继续向下走直到到达结尾，您将访问的链接列表的元素。如果列表不包含循环，则所有这些值都是不同的。但是，如果它确实包含一个循环，那么这个序列将无休止地重复。

这是使 Floyd 算法起作用的定理:

The linked list contains a cycle if and only if there is a positive integer j such that for any positive integer k, x_j = x_jk.

让我们去证明这一点；这并不难。对于“如果”的情况，如果这样的 j 存在，则选择 k = 2。那么对于某些正 j，我们有 x_j = x_2j 并且 j ≠ 2j，因此列表包含一个循环。

对于另一个方向，假设列表包含从位置 s 开始的长度为 l 的循环。设 j 是 l 大于 s 的最小倍数。那么对于任何k，如果我们考虑x_j和x_jk，因为j是循环长度的倍数，我们可以认为x_jk> 作为从列表中的位置 j 开始，然后执行 j 步 k-1 次而形成的元素。但是每次你采取 j 步，你最终都会回到你在列表中开始的地方，因为 j 是循环长度的倍数。因此，x_j = x_jk。

这个证明向您保证，如果您在每次迭代中采取任何恒定的步数，您确实会碰到慢指针。更准确地说，如果你在每次迭代中采取 k 步，那么你最终会找到点 x_j 和 x_kj 并检测循环。直觉上，人们倾向于选择 k = 2 来最小化运行时间，因为您在每次迭代中采取的步骤最少。

我们可以更正式地分析运行时如下。如果列表不包含循环，则快速指针将在 O(n) 时间内执行 n 步后到达列表末尾，其中 n 是列表中元素的数量。否则，慢指针走了j步后，两个指针就会相遇。请记住，j 是 l 大于 s 的最小倍数。如果 s ≤ l，则 j = l；否则如果 s > l，则 j 最多为 2s，因此 j 的值为 O(s + l)。由于 l 和 s 不能大于列表中的元素数，这意味着 j = O(n)。但是，在慢指针执行了 j 步之后，对于慢指针执行的每 j 步，快指针将执行 k 步，因此它将执行 O(kj) 步。由于 j = O(n)，净运行时间至多为 O(nk)。请注意，这表示我们使用快速指针执行的步骤越多，算法完成所需的时间就越长(尽管只是按比例计算)。因此，选择 k = 2 可以最大限度地减少算法的整体运行时间。

希望这对您有所帮助!