algorithm - 弗洛伊德循环检测的运行时复杂度

Question

根据一些在线资源，我提到了 Floyd 循环检测算法的运行时复杂度为 O(n)。说，

p = slow pointer
q = fast pointer
m = the distance from start of linked list to first loop node
k = the distance of the meeting point of fast and slow nodes from the first loop node 
l = length of loop
rp = number of loop rotations by p before meeting q.
rq = number of loop rotations by q before meeting p.

运行时间复杂度应该是=m+rp*l+k这个值怎么是O(n)？

Answer 1

如果列表有N个节点，那么在<= N步中，要么快速指针会找到列表的末尾，要么有一个循环和慢指针将在循环中。

假设循环的长度为M <= N:一旦慢指针进入循环，快指针和慢指针都将永远停留在循环中。每一步，快慢指针之间的距离都会增加1。当距离被M整除时，快慢指针将在同一个节点上，算法终止。距离将在 <= M 步内达到可被 M 整除的数字。

因此，让慢指针指向循环，然后让快指针和慢指针相遇需要 <= N + M <= 2N 步骤，也就是在 O( N)

事实上，如果您注意到当存在循环时，慢速指针将在 N - M 步中到达它，那么您可以获得更严格的步数限制，因此总步数是 <= N。