請教大家一個問題.
有一個陣列 x[2N] 要將其內容根據某個排列規則做 permutation.
規則如下:
x[0] -> x[0];
x[1] -> x[N];
x[2] -> x[1];
x[3] -> x[N+1];
:
:
x[2k] -> x[k];
x[2k+1] -> x[N+k];
:
:
x[2N-2] -> x[N-1]
x[2N-1] -> x[2N-1]
(0 <= k < N)
就是將 x 的偶數項依序放到 x[0 ~ N-1],
將 x 的奇數項依序放到 x[N ~ 2N-1].
希望能夠做到時間複雜度為 O(N), 這顯然很容易辦到.
但是我又希望空間複雜度能夠是 O(1), 也就是不可以有隨 N 而變大的暫存變數.
這是否有可能辦到?
感覺上似乎和離散數學裡面的 permutation group 有關?
想請教大家的想法. 謝謝. :)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.64.148.4