作者聲稱這個置換演算法的時間復雜度：
from collections import deque
def find_permutations(nums):
nums_l = len(nums)
perms = deque()
perms.append([])
for num in nums: # (1)
for _ in range(len(perms)): # (2)
perm = perms.popleft()
for j in range(len(perm) 1): # (3)
new_perm = list(perm) # (4)
new_perm.insert(j, num) # (5)
perms.append(new_perm) # (6)
return perms
是 n*n!
但我不明白為什么。這是我對每一行代碼的時間復雜度的計算：
(1): len(nums) ~ n
(2): len(perms) ~ n!
(3): len(perm) ~ n
(4): n
(5): n
(6): n
所以總時間復雜度為：
n * n! * n * (n n n) ~ n^3 * n!
我錯了嗎？
uj5u.com熱心網友回復：
在進入主要問題之前，步驟（6）有一個小錯誤：append是 O(1)。但這并不影響整體的復雜性。
您的分析在第 (2) 步出錯：
for _ in range(len(perms)):
這不會執行 O(n!) 次迭代。第一次它甚至只執行1次迭代，第二次仍然是1次迭代，第三次2次迭代，然后2 * 3，然后2 * 3 * 4，......最后一次（n-1）！迭代。
那么在步驟（3）也存在高估：
for j in range(len(perm) 1)
的大小perm最初很小（對應于步驟 2 的回圈）：首先排列的大小為 0，然后在外回圈的下一次迭代中，它們的大小為 1，...然后是 2，...向上到 n-1。
所以對于內回圈的總迭代次數，我們有這個總和：
1 * 1 1 * 2 2 * 3 (2 * 3) * 4 ... k！ ... n！
看待這一點的一種更簡單的方法是認識到，在外回圈的每次迭代中，此代碼生成的所有排列都比前一次迭代長一個專案。因此，在第一次迭代中，您將獲得大小為 1（使用第一個輸入值）的所有排列，在第二次迭代中，您將獲得大小為 2（使用兩個第一個輸入值）的所有排列，等等。這是一種自下而上的方法。另請注意，popLeft執行正確的次數以洗掉前一次（外部）迭代的所有排列，而append對所有新排列執行（僅在下一次外部迭代中彈出）。
所以我們現在可以很容易地看到append執行了這個次數：
1！ 2！ 3！ 4！ ... n！= O(n!)
如果我們現在將第 4 步的復雜性（“吸收”第 5 步的復雜性）包含在其中，那么我們得到：
1.1！ 2.2！ 3.3！ 4.4！ ... 唔！= O(nn!)
uj5u.com熱心網友回復：
該演算法通過將數字插入現有排列的所有可能位置來生成排列
現在第一個回圈顯然是 O(n)
讓我們看看其他回圈發生了什么：
最后一次迭代（最壞的情況）：
- 遍歷所有
(n-1)!排列（使用先前的迭代生成）-O((n-1)!) - 復制它們中的每一個并在里面添加新數字 -
O(n)每個
總的來說，它(n-1)! * (n) = n!是其他回圈的最壞情況
所以O(n * n!)總體來說
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/355678.html
下一篇：解決回圈依賴的演算法？