https://www.youtube.com/watch?v=pKO9UjSeLew&ab_channel=JomaTech
증명
Xi = 토끼와 거북이가 만난 지점
i = 토끼와 거북이가 만나기 까지 거북이가 이동한거리
Xμ = 사이클 시작지점
μ = 리스트 시작지점부터 사이클 시작점까지 거리
λ = 사이클의 순환길이
m = 거북이가 사이클을 돈 횟수
n = 토끼가 사이클을 돈 횟수
y = xi에서 xμ사이의 거리
거북이의 이동거리
i = μ + (m * λ) + y -- 1
거북이의 두배로 이동하는 토끼의 이동거리
2i = μ + (n * λ) + y -- 2
1과 2의 연립방정식
i = (n - m) * λ -- 3
사이클내 임의의 점 xj ( j >= μ )는 사이클의 임의(k)만큼 회전해도 같은점
Xj = X(j + k * λ)
j = μ, k = (n - m) 대입
Xμ = X(μ + (n - m) * λ)
Xμ = X(μ + (n - m) * λ)
3번 식에서 (n - m) * λ = i 이기에
xμ = x(μ + i)
따라서 μ와 xi에서 μ의 거리가 같다는것을 증명
Sudo
def floyd(f, x0):
# Main phase of algorithm: finding a repetition x_i = x_2i.
# The hare moves twice as quickly as the tortoise and
# the distance between them increases by 1 at each step.
# Eventually they will both be inside the cycle and then,
# at some point, the distance between them will be
# divisible by the period λ.
tortoise = f(x0) # f(x0) is the element/node next to x0.
hare = f(f(x0))
while tortoise != hare:
tortoise = f(tortoise)
hare = f(f(hare))
# At this point the tortoise position, ν, which is also equal
# to the distance between hare and tortoise, is divisible by
# the period λ. So hare moving in circle one step at a time,
# and tortoise (reset to x0) moving towards the circle, will
# intersect at the beginning of the circle. Because the
# distance between them is constant at 2ν, a multiple of λ,
# they will agree as soon as the tortoise reaches index μ.
# Find the position μ of first repetition.
mu = 0
tortoise = x0
while tortoise != hare:
tortoise = f(tortoise)
hare = f(hare) # Hare and tortoise move at same speed
mu += 1
# Find the length of the shortest cycle starting from x_μ
# The hare moves one step at a time while tortoise is still.
# lam is incremented until λ is found.
lam = 1
hare = f(tortoise)
while tortoise != hare:
hare = f(hare)
lam += 1
return lam, mu
이 코드는 포인터, 함수 평가 및 동등성 테스트를 저장하고 복사하는 방식으로만 시퀀스에 액세스합니다. 따라서 포인터 알고리즘으로 적합합니다. 알고리즘은 이러한 유형의 O ( λ + μ ) 작업과 O (1) 저장 공간을 사용합니다.