Cycle Finding

Cycle Finding: a self-mapped function in a finite set

尋找有限集自身映射函數的循環週期:給定一個有限集中的元素做為起點,不斷映射,必會循環,找出此循環的起始點元素、此循環的最小週期、進入此循環前的映射次數。

應用

1. 檢查一條singly linked list是否因接錯而造成無限循環,並找出接錯位置。
2. 檢查兩條獨立的singly linked list是否因接錯而牽連作伙,並找出接錯位置。
3. 一條陣列連續放著n+1個數,數值皆介於1到n,
   其中恰有兩數相同,請找出此數及此數位置。
4. 檢查自動機是否有無窮迴圈。
5. 兩整數相除得到之無限小數,請找出其循環節。

一個簡單的演算法(Memoization)

開一個陣列,記錄每個元素是否拜訪過,如果又遇到已拜訪過的元素,那就表示有循環了。

這個方法簡單又有效率,不過缺點就是記憶體用很兇。時間複雜度O(N),空間複雜度O(N),N為集合大小。

UVa 202 275 517

Cycle Finding: Floyd's Algorithm
(Tortoise and Hare Algorithm)

龜兔賽跑演算法

這個演算法的好處是空間很省,僅僅以龜兔兩個變數就能找出循環。時間複雜度是O(s+p),s為進入此循環前的映射次數,p為循環的最小週期。空間複雜度為O(1)。

UVa 350