就是那個把A_1,B_1,A_2,B_2,...,A_n,B_n用constant memory和linear time重排成A_1,A_2,...,A_n,B_1,B_2,...,B_n的題，似乎還沒人給出解答。我來拋磚引玉一下吧。
首先先假設n是2^k的形式，並且把下標從0開始，那麽每個下標都是一個k bit的整數。這樣做的好處在於一個很關鍵的observation：我們要實現的置換就是把每一個下標為(r_1,r_2,...r_k)的數，移動到(r_k,r_1,r_2,r_3,...,r_{k-1})，也就是說，shift right by 1。這樣子我們就隱式的表達了這個permutation，而且是一個很好的closed form。
先假設我們已經解決了n=2^k的情況，那麽對於一般的n怎麽辦呢？很簡單，把n拆分成2的方冪，分別求解，然後merge。不難看出要merge長度為x和y的數組隻需要O(x+y)的時間，總共的merge的時間也就是linear的。
那麽再回到n=2^k的情況，雖然找出了一個很好的representation，但並沒有解決整個問題。從上麵的置換，不難看出拆分成輪換之後的結構。現在的難題在於，對於每個輪換我們隻想算一次。也就是說，當處理一個新的下標的時候，我們想知道，它是否已經出現在了之前的輪換中了呢？一個簡單的辦法是求出每個輪換的最小表示，也就是其中最小的那個下標。隻有在處理這個最小下標的時候才進行數組的輪換操作。然而，要判斷一個下標是否是所在輪換裏最小的那個，需要O(k)的操作，也就是說算法的時間是O(nlogn)的。
那麽怎樣達到O(n)呢？有很多可能性。比如說，能否用constant time判斷最小表示（或者用constant time去update）？或者，並不一定以下標從小到大的順序update，而是找一個更方便處理的順序。又或者，如果就用naive的方法判斷每個下標是否最小表示，找到一個更小的下標就停，那麽amortized time是多少呢？有可能會是O(nloglogn)。總之，還有很多可能的方向，我沒來得及細想。就先寫在這裏，做為拋磚引玉吧。
首先先假設n是2^k的形式，並且把下標從0開始，那麽每個下標都是一個k bit的整數。這樣做的好處在於一個很關鍵的observation：我們要實現的置換就是把每一個下標為(r_1,r_2,...r_k)的數，移動到(r_k,r_1,r_2,r_3,...,r_{k-1})，也就是說，shift right by 1。這樣子我們就隱式的表達了這個permutation，而且是一個很好的closed form。
先假設我們已經解決了n=2^k的情況，那麽對於一般的n怎麽辦呢？很簡單，把n拆分成2的方冪，分別求解，然後merge。不難看出要merge長度為x和y的數組隻需要O(x+y)的時間，總共的merge的時間也就是linear的。
那麽再回到n=2^k的情況，雖然找出了一個很好的representation，但並沒有解決整個問題。從上麵的置換，不難看出拆分成輪換之後的結構。現在的難題在於，對於每個輪換我們隻想算一次。也就是說，當處理一個新的下標的時候，我們想知道，它是否已經出現在了之前的輪換中了呢？一個簡單的辦法是求出每個輪換的最小表示，也就是其中最小的那個下標。隻有在處理這個最小下標的時候才進行數組的輪換操作。然而，要判斷一個下標是否是所在輪換裏最小的那個，需要O(k)的操作，也就是說算法的時間是O(nlogn)的。
那麽怎樣達到O(n)呢？有很多可能性。比如說，能否用constant time判斷最小表示（或者用constant time去update）？或者，並不一定以下標從小到大的順序update，而是找一個更方便處理的順序。又或者，如果就用naive的方法判斷每個下標是否最小表示，找到一個更小的下標就停，那麽amortized time是多少呢？有可能會是O(nloglogn)。總之，還有很多可能的方向，我沒來得及細想。就先寫在這裏，做為拋磚引玉吧。
選擇“Disable on www.wenxuecity.com”
選擇“don't run on pages on this domain”
