如何確定Python中遞歸循環的時間複雜度？

在Python中生成列表的所有排列的時間複雜度是多少？以下代碼是需要計算其時間複雜度的代碼。我該怎麼做呢？如何確定Python中遞歸循環的時間複雜度？

def permute(list): 
    tot_list = [] 
    if len(list) == 1: 
     return [list] 
    for permutation in permute(list[1:]): 
     for i in range(len(list)): 
      tot_list.append(permutation[:i] + list[0:1] + permutation[i:]) 
    return tot_list

來源

2013-05-04 Yannick Maris

分析此函數的主要挑戰是沒有那麼多的遞歸調用，但每次調用都會返回一個逐漸增大和增大的元素列表。特別要注意的是，有n！ n個元素列表的排列。因此，我們知道如果你在一個大小爲n的列表上進行遞歸調用，將會有n！元素返回。

讓我們來看看這將如何影響運行時。如果只有一個元素的列表，則時間複雜度爲O（1）。否則，我們假設在列表中有n + 1個元素。算法然後

在大小爲n的列表上進行遞歸調用。
對於返回的每個元素，將列表的第一個元素拼接到所有可能的位置。
返回結果。

我們可以通過看在遞歸的每一層所做的工作，這意味着我們將重點放在步驟（2）和（3）現在分析遞歸總運行時間。

請注意，在步驟2中，如果列表中有n + 1個元素，我們將不得不查看n！遞歸調用產生的排列。每個排列都有n個元素。對於每個排列，我們創建n + 1個新列表，其中每個列表都有n + 1個元素。因此，我們有n！循環迭代，每個循環都有（n + 1）的工作。因此，這個級別完成的總工作量（大致）爲（n + 1）＆middot; ñ！我們可以注意到（n + 1）＆middot; N！ =（n + 1）!,所以完成的工作可以寫成（n + 1）（n + 1）！。這嚴格小於（n + 2）！，所以我們可以說在有n + 1個總元素時所做的工作是O（（n + 2）！）。（注意，我們不能說這是O（n！），因爲n！= o（（n + 2）！））。

所以，現在我們可以說，所做的總功是（粗略地講）由

1給出！ + 2！ + 3！ + ... +（n + 1）！

據我所知，這沒有一個很好的封閉式公式。但是，我們可以注意到，

1！ + 2！ + 3！ + ... +（n + 1）！

<（n + 1）！ +（n + 1）！ + ... +（n + 1）！

=（n + 2）（n + 1）！

=（n + 2）！

所以整體表達式是O（（n + 2）！）。同樣，我們有

1！ + 2！ + 3！ + ... +（n + 1）！

>（n + 1）！

所以整體表達式是Ω（（n + 1）！）。換句話說，真正的答案夾在（n + 1）之間的某個地方（漸近地）！和（n + 2）!.因此，運行時間會快速增長。

希望這會有所幫助！

來源

2013-05-04 18:06:39 templatetypedef

+1因子彈出並不奇怪，因爲有n！ n個元素的排列。 – delnan 2013-05-04 19:33:28

如何確定Python中遞歸循環的時間複雜度？

回答

相關問題