Algorithm 演算法 - 判圈系列 Brent 判圈算法(傳送龜算法)

簡介 Intro 根據演算法期會比 Floyd 的方式快 24-36% 的速度。 解釋 這個演算法的方式其實基本上跟 Floyd 不一樣的地方在於龜兔的移動方式。在 Floyd 的演算法中，龜兔會一起移動，只是步數的不同。但在 Brent 的演算法中，只有兔子在移動。 每次兔子移動後，烏龜會馬上傳送到跟兔子一樣的位置（所以才叫 Teleporint Turtle）。然後兔子在將步數倍增移動。例如兔子第一次移動 1 格、再來 2 格、4 格一直走到底或是遇到烏龜。 進階題目 找出迴圈長度 當相遇...