我在簡化此遞回演算法的時間復雜度以查找給定輸入集的冪集時遇到了麻煩。到目前為止，我也不完全確定我所得到的是否正確。
它在此鏈接的頁面底部進行了描述：http : //www.ecst.csuchico.edu/~akeuneke/foo/csci356/notes/ch1/solutions/recursionSol.html
通過考慮函式為任意選擇的大小為 4 的輸入集所采取的每一步，然后將其轉換為大小為 n 的輸入集，我得出的結果是，該演算法的大 O 表示法的時間復雜度為： 2 n n n
這個對嗎？有沒有一種特定的方法可以找到遞回函式的時間復雜度？
uj5u.com熱心網友回復：
運行時間實際上是 O(n*2 n )。簡單的解釋是，這是一種漸近最優演算法，因為它所做的總作業由創建直接在演算法的最終輸出中作為特征的子集主導，生成的輸出的總長度為 O(n*2 n）。我們還可以分析偽代碼的注釋實作（在 JavaScript 中）以更嚴格地顯示這種復雜性：
function powerSet(S) {
if (S.length == 0) return [[]] // O(1)
let e = S.pop() // O(1)
let pSetWithoutE = powerSet(S); // T(n-1)
let pSet = pSetWithoutE // O(1)
pSet.push(...pSetWithoutE.map(set => set.concat(e))) // O(2*|T(n-1)| ||T(n-1)||)
return pSet; // O(1)
}
// print example:
console.log('{');
for (let subset of powerSet([1,2,3])) console.log(`\t{`, subset.join(', '), `}`);
console.log('}')其中T(n-1)表示對 n-1 個元素的遞回呼叫的運行時間，|T(n-1)|表示遞回呼叫回傳的冪集中子集的數量，并||T(n-1)||表示遞回呼叫回傳的所有子集中的元素總數。
用這些術語表示的復雜度線對應于2.偽代碼步驟的第二個要點：回傳沒有 element 的e冪集的s并集，以及每個子集與并集的相同冪集e：
(1) U ((2) = {s in (1) U e})
這個聯合是在 push 和 concat 操作方面實作的。該push做的工會(1)與(2)在|T(n-1)|隨著時間的|T(n-1)|新亞群被聯合在一起到電源集。的地圖concat操作是負責產生(2)通過附加e到的每一個元素pSetWithoutE中|T(n-1)| ||T(n-1)||的時間。第二個復雜性對應于（根據定義）||T(n-1)||的|T(n-1)|子集存在元素pSetWithoutE，并且每個子集的大小增加 1。
然后我們可以n用這些術語表示輸入大小的運行時間：
T(n) = T(n-1) 2|T(n-1)| ||T(n-1)|| 1; T(0) = 1
可以通過歸納證明：
|T(n)| = 2n
||T(n)|| = n2n-1產生：
T(n) = T(n-1) 2*2n-1 (n-1)2n-2 1; T(0) = 1當您決議地求解此遞推關系時，您將得到：
T(n) = n 2n n/2*2n = O(n2n)它與最佳功率集生成演算法的預期復雜度相匹配。遞推關系的解也可以直觀的理解：
n 次迭代中的每一次都在生成冪集的新子集之外執行 O(1) 作業，因此n是最終運算式中的項。
就生成冪集的每個子集所做的作業而言，每個子集在通過 concat 生成后都會被推送一次。推入了2 n個子集，產生了 2 n項。每個子集的平均長度為 n/2，組合長度為 n/2*2 n，對應于所有 concat 操作的復雜度。因此，總時間由 n 2 n n/2*2 n 給出。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/384449.html