2

リストで動作する再帰関数があります。関数には、それ自体が呼び出されるループが含まれており、別の関数で終了しますg。その構造は次のように類似しています。問題を単純化するために、l常に要素が重複していないリストであると想定できます。

let rec f l = function
  | [] -> g ()
  | _ ->
      List.fold_left
        (fun acc x ->
           let lr = List.filter (fun a -> (a <> x)) l in
           acc + (f lr))
        1 l

List.length lこの関数の複雑さをと の複雑さで表現する方法がわかりませんg。

gの複雑さと階乗に比例すると思いますがList.length l、誰か確認できますか?

4

2 に答える 2

1

リストには重複が含まれていないと想定しているためl、この関数は、元のリストよりも要素が1つ少ないすべてのサブリストを計算し、それらすべてに対して再帰的に呼び出します。したがって、サイズngのリストから開始するときに呼び出される回数はg ？（n）= n・g ？（n-1）= n！

それでは、関数が実行しなければならない他のすべてについて考えてみましょう。再帰の各ステップでの作業量には、次のものが含まれます。

  • 元のリストの要素ごとに、1つ少ない要素の新しいリストを作成します。これは、 n2に等しい作業の合計量です。
  • 再帰呼び出しの結果がわかったら、それをアキュムレータに追加します。これは、 nに等しい作業の合計量です（フィルターのコストが高くなるため、この部分は無視できます）。

したがって、（以前の分析に基づいて）各再帰ステップが呼び出される回数がわかっているので、g関連のない作業の合計量は次のようになります。（n）= n 2 + n（n-1）2 + n（n-1）（n-2）2 + ... + n！

この式は苦痛のように見えますが、実際にはt ？（n）/ n！nが増加するにつれて有限の非ゼロ制限があり（これは、 0<k<nでのk+1 / k！の合計です）、したがってt ？（n）=Θ（n！）。

于 2012-06-08T08:31:31.640 に答える
1

わかった。私は不信感を抱いているように見えるつもりはありません。これはあまり実用的なコードではないため、関数型プログラミングの宿題のように見えます。

F(n) を長さ n の入力に対する比較の数と加算の数とします。そして、G を g の実行時間とします。g はオペランドを取らないので、G は定数です。呼び出された回数を数えているだけです。

フォールドはその関数を n 回実行します。実行ごとに filter を呼び出して n 回の比較を行い、毎回入力から 1 つの要素を削除してから、この短縮されたリストに対して f を再帰的に呼び出し、1 つの追加を行います。したがって、総費用は

F(n) = n * (n + F(n - 1) + 1) [n > 0 の場合] = G [それ以外の場合]

最初の項は次のように展開されます

F(n) = n * F(n - 1) + n^2 + n

あなたが提案したように、これは O(n! + n^3 + n^2 + nG) = O(n! + nG) です。

これがお役に立てば幸いです。

于 2012-06-06T05:19:56.927 に答える