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