順列ランタイム分析：次のように反復DPソリューション

Question

マイ反復DPソリューションです：

def permutations(string): 
    # let n = len(string) 
    N = [[] for _ in range(len(string) + 1)] # O(n) 

    N[0].append("") 

    for i in range(1, len(string) + 1): # O(n) 
     N[i] = [perm[:j] + string[i - 1] + perm[j:] for j in range(i) for perm in N[i - 1]] # O(???) 

    return N[-1] 

しかし、私は上記のプログラムの実行時間を分析し、トラブルを抱えています。具体的には、行for perm in N[i - 1]のランタイムの境界を設定します。私は再帰的解がO(n!)であることを知っていますが、再帰的な実行時間を知らずに上記のプログラムの実行時間を見つける方法はありますか？

Answer 1

は、私たちの主な関心として

N[i] = [perm[:j] + string[i - 1] + perm[j:] for j in range(i) for perm in N[i - 1]] 

を考えてみましょう。私たちは、今

line 1: for i in range(1, len(string) + 1):      # O(n) 
line 2:  N[i] = []           # O(n) 
line 3:  for j in range(i):         # O(sum i from 1 to n) 
line 4:   for perm in N[i - 1]:       # O(sum len(Ni) from 1 to n) 
line 5:    N[i].append(perm[:j] + string[i - 1] + perm[j:]) 

としてそれを書き換えることができます

、i = 1ため、line 3とline 4はstring[0]の単一の要素でN[1]を残して、単一の時間を実行します。

i = 2について、line 3二度実行されますとline 4は、3つの要素とN[2]を残して、第二のための最初の実行と2のための単一の時間を実行します。

パターンを確認しますか？早送りができます。 6、24、120、720

N total runs diff 
1 1   1 
2 3   2 
3 9   6 
4 33   24 
5 153   120 
... 

だから我々は以来、それは（https://math.stackexchange.com/questions/227551/）かなり複雑ですが、我々はそれがO(n!)境界内で確保することができます簡素化

n 
____ 
\ 
    > k! 
/___ 
k = 0  (asciiart courtesy of sympy) 

の総複雑さを取得1からnまでのk*k!の合計は(n+1)! - 1であるので、総実行時間はO(n!),となり、既知の再帰的ランタイムに依存することはありません。