52

私は学校で時間の複雑さを勉強していますが、私たちの主な焦点は、多項式時間 O(n^c)アルゴリズムと準線形時間 アルゴリズムにあり、ランタイムの観点の例としてO(nlog(n))時折指数時間アルゴリズムを使用しているようです。 O(c^n)ただし、より大きな時間の複雑さを扱うことは決してカバーされませんでした。

factorial time で実行されるアルゴリズム ソリューションの問題の例を見たいと思いますO(n!)。このアルゴリズムは、問題を解決する単純なアプローチかもしれませんが、階乗時間で実行するために人為的に肥大化することはできません。

階乗時間アルゴリズムが問題を解決するための最もよく知られているアルゴリズムである場合は、追加の信頼性があります。

4

4 に答える 4

63

リストのすべての順列を生成する

あなたはn!リストを持っているので、より良い効率を達成することはできませんO(n!).

于 2013-05-15T02:59:35.187 に答える
29

巡回セールスマンには O(n!) の単純な解がありますが、O(n^2 * 2^n) の動的計画法の解があります。

于 2013-05-15T02:51:20.817 に答える
8

配列のすべての順列のリストは O(n!) です。以下は、swap メソッドを使用した再帰的な実装です。再帰は for ループ内にあり、配列内の要素は、要素がなくなるまで位置が入れ替わります。結果カウントからわかるように、配列の要素数は n! です。各順列は操作であり、n! オペレーション。

def permutation(array, start, result)
    if (start == array.length) then
        result << array.dup  
    end
    for i in start..array.length-1 do
        array[start], array[i] = array[i], array[start]
        permutation(array, start+1,result)
        array[start], array[i] = array[i], array[start]
    end 
    result   
end        


p permutation([1,2,3], 0, []).count  #> 6 = 3!
p permutation([1,2,3,4], 0, []).count #> 24 = 4!
p permutation([1,2,3,4,5], 0, []).count #> 120 = 5!
于 2015-08-03T17:01:31.900 に答える