0

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
4

1 に答える 1

6

この関数を分析する上での主な課題は、再帰呼び出しがそれほど多くないことですが、各呼び出しは徐々に大きくなる要素のリストを返します。特に、n! があることに注意してください。n 要素のリストの順列。したがって、サイズ n のリストに対して再帰呼び出しを行うと、n 個になることがわかります。要素が返されました。

それでは、これがランタイムにどのように影響するかを見てみましょう。要素が 1 つだけのリストがある場合、時間計算量は O(1) です。それ以外の場合は、リストに n + 1 個の要素があるとします。そのときのアルゴリズム

  1. サイズ n のリストに対して再帰呼び出しを行います。
  2. 返された要素ごとに、可能なすべての位置でリストの最初の要素をスプライスします。
  3. 結果を返します。

再帰の各レベルで行われた作業を見るだけで、再帰の合計実行時間を分析できます。つまり、ここではステップ (2) と (3) に焦点を当てます。

ステップ 2 で、リストに n + 1 個の要素がある場合、n を見なければならないことに注意してください。再帰呼び出しによって生成された順列。これらの各順列には n 個の要素があります。順列ごとに、n + 1 個の新しいリストを作成します。それぞれのリストには n + 1 個の要素が含まれます。したがって、n! ループ反復、それぞれが (n + 1) 2の作業を行います。したがって、このレベルで行われる総作業量は (おおよそ) (n + 1) 2 · n!です。(n + 1) · n! = (n + 1)! なので、行われた作業は (n + 1)(n + 1)! と書くことができます。これは厳密には (n + 2)! よりも小さいため、合計要素数が n + 1 の場合に行われる作業は O((n + 2)!) であると言えます。(n! = o((n + 2)!) であるため、これが O(n!) であるとは言えないことに注意してください)。

これで、完了した作業の合計は (大まかに言えば) によって与えられると言えます。

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-04T18:06:39.813 に答える