我試圖了解用于生成陣列排列的演算法的時間和空間復雜度。給定一個部分構建的排列，其中已經選擇k了n元素，演算法k 1從剩余n-k元素中選擇元素并呼叫自身來選擇剩余n-k-1元素：
public static List<List<Integer>> permutations(List<Integer> A) {
List<List<Integer>> result = new ArrayList<>();
permutations(A, 0, result);
return result;
}
public static void permutations(List<Integer> A, int start, List<List<Integer>> result) {
if(A.size()-1==start) {
result.add(new ArrayList<>(A));
return;
}
for (int i=start; i<A.size(); i ) {
Collections.swap(A, start, i);
permutations(A, start 1, result);
Collections.swap(A, start, i);
}
}
我的想法是，在每次呼叫中，我們交換集合的元素2n時間，其中n是要置換的元素數量，并進行n遞回呼叫。所以運行時間似乎符合遞回關系T(n)=nT(n-1) n=n[(n-1)T(n-2) (n-1)] n=...=n n(n-1) n(n-1)(n-2) ... n!=n![1/(n-1)! 1/(n-2)! ... 1]=n!e，因此時間復雜度為O(n!)，空間復雜度為O(max(n!, n))，其中n!是排列總數，n是遞回樹的高度。
這個問題是從編程訪談預定元素取，和他們說，時間復雜度是O(n*n!)因為“函式呼叫數C(n)=1 nC(n-1)... [它解決到] O(n!)... [和] ...我們做的O(n)每個計算在遞回呼叫之外呼叫”。
哪個時間復雜度是正確的？
uj5u.com熱心網友回復：
該演算法的時間復雜度，以執行的基本運算元計算，為Θ(n * n!)。考慮result演算法終止時串列的大小——它包含n!排列，每個長度為n，并且我們無法n * n!在少于該時間量的時間內創建一個包含總元素的串列。空間復雜度是一樣的，因為遞回堆疊一次只有一次O(n)呼叫，所以輸出串列的大小決定了空間復雜度。
如果您只計算對 的遞回呼叫次數permutations()，則該函式將被呼叫O(n!)次數，盡管這通常不是沒有進一步說明的“時間復雜度”的含義。換句話說，您可以及時生成所有排列O(n!)，只要您在它們生成后不讀取或寫入這些排列即可。
運行時推導失敗的部分是 T(n) 的定義。如果您將 T(n) 定義為“permutations(A, start)輸入 A 具有長度時的運行時間n”，則您不能根據 T(n-1) 或 T() 的任何其他函式遞回地定義它，因為所有遞回呼叫中輸入n的長度為 ，A 的長度。
定義 T(n) 的一種更有用的方法是將其指定為 的運行時間permutations(A', start)，當 A' 是固定的初始陣列 A和 A.length - start == n 的任何排列時。在這里寫遞回關系很容易：
T(x) = x * T(x-1) O(x) if x > 1
T(1) = A.length
這考慮到最后一個遞回呼叫 T(1) 必須執行O(A.length)作業以將該陣列復制到輸出的事實，并且這個新的遞回給出了教科書的結果。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/359132.html
上一篇：開始迷宮的細胞