※ 引述《jeunder ()》之銘言：
: 就是將 x 的偶數項依序放到 x[0 ~ N-1],
: 將 x 的奇數項依序放到 x[N ~ 2N-1].
: 希望能夠做到時間複雜度為 O(N), 這顯然很容易辦到.
: 但是我又希望空間複雜度能夠是 O(1), 也就是不可以有隨 N 而變大的暫存變數.
: 這是否有可能辦到?
: 感覺上似乎和離散數學裡面的 permutation group 有關?
: 想請教大家的想法. 謝謝. :)
如果只是不要有隨 N 變大的暫存變數，則可以用遞迴。
以下的方法應該是空間 O(logN), 時間 O(N*logN), 不使用變動大小的暫存變數。
但若站在技術性的實用的立場，可能還是我的上一個方法比較好。
而相對於那個漂亮的 space O(1), time O(N^2) 轉置矩陣方法，在 N = 1000 時
swap 數量為 8188 : 499500.
---------------------------------------------------------------------
#include <stdio.h>
#include <malloc.h>
int* x;
int n;
int k = 0;
void swap(int* d, int a, int b) { int t = d[a]; d[a] = d[b], d[b] = t; k++; }
void p(int* d, int c) {
int t = c / 2;
int e = (t + 1) % 2;
int i;
for(i = 0; i < t; i += 2) swap(d, i, i + t + e);
if(e) for(i = 0; i < c; i += 2) swap(d, i, i + 1);
if(t < 3) return;
p(d + e, t - 1 - e);
p(d + t + 1, t - 1 - e);
}
void main(int argc, char* argv[]) {
int i, t;
if(argc < 2) return;
sscanf(argv[1], "%d", &t); if(t <= 0) return;
n = t * 2;
x = malloc(n * sizeof(int));
for(i = 0; i < n; i++) x[i] = i;
p(x + 1, n - 2);
printf("swap number = %d\n", k);
}
--
※ 編輯: semop 來自: 59.116.1.213 (11/23 01:29)