※ 引述《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)