Algoritma pencari-siklus Floyd

Algoritme pencari-siklus Floyd adalah algoritme untuk mencari siklus dalam barisan bilangan (disebut juga sekuens). Sekuens yang dimaksud bisa berupa yang tersimpan dalam struktur data ataupun dibuat sesuai kebutuhan (berupa rumus). Algoritme ini ditemukan Robert W. Floyd pada tahun 1967. Nama lainnya ialah algoritme "tortoise and the hare" (istilah ini serupa dengan "kura-kura dan kancil").

Algoritma pencari-siklus Floyd

Perlu diperhatikan bahwa "Algoritme Floyd" berbeda dengan "Algoritme pencari-siklus Floyd" dari penemu yang sama.

Algoritme

sunting

Misalkan kita ingin memeriksa sebuah sekuens ai. Kita definisikan sang kura-kura sebagai:

 

dan sang kancil sebagai

 

di mana i elemen bilangan asli.

Jalankan dengan i dimulai dari 1, berlanjut ke 2, dst sampai kondisi ini terjadi

 
 

Kondisi ini akan berlaku untuk   di mana s adalah siklus yang dicari.