1

私はアルゴリズム分析と SML に不慣れで、次の SML 関数の平均的なケースの実行時間に夢中になりました。私の考えに対するフィードバックをいただければ幸いです。

fun app([]) = []
  | app(h::t) = [h] @ app(t)

したがって、すべての再帰の後、一連の単一要素リスト (および 1 つの要素なしリスト) になります。

[1]@[2]@[3]@...@[n]@[]

は元のリストの要素nの数であり、元のリスト1, 2, 3, ..., nのどの要素について話しているかを示すためのものです。L @ Rリスト L の長さに比例して時間がAかかります。 @ がすべての要素にかかる一定の時間であると仮定すると、次のように想像できます。

[1,2]@[3]@[4]@...@[n]@[] took 1A
[1,2,3]@[4]@...@[n]@[]   took 2A
[1,2,3,4]@...@[n]@[]     took 3A
...
[1,2,3,4,...,n]@[]       took (n-1)A
[1,2,3,4,...,n]          took nA

したがって、時間の繰り返しは次のようになると考えています。

T(0) = C                 (if n = 0)
T(n) = T(n-1) + An + B   (if n > 0)

どこCは基本ケースの最終的な一致でありapp([])、Bの定数ですh::t。再帰を閉じると、次のようになります (証明は省略)。

T(n) = (n²+n)A/2 + Bn + C = (A/2)n² + (A/2)n + Bn + C = Θ(n²)

これは、私に提示された答えとは異なる私自身の結論です。

T(0) = B                 (if n = 0)
T(n) = T(n-1) + A        (if n > 0)

クローズドフォーム

T(n) = An + B = Θ(n)

これはかなり異なります。(Θ(n) 対 Θ(n²)!) しかし、これL @ Rは線形ではなく一定の時間がかかると仮定していませんか? たとえば、追加の場合は true になります。

fun add([]) = 0
  | add(h::t) = h + add(t) (* n + ... + 2 + 1 + 0 *)

または連結さえ

fun con([]) = []
  | con(h::t) = h::con(t)  (* n :: ... :: 2 :: 1 :: [] *)

存在する方法を誤解していL @ Rますか、それとも私の分析は（少なくともある程度）正しいですか？

4

1 に答える 1

1

はい。コマンドを一度に 1 つの関数呼び出しで手動で実行すると、app [1,2,3]次のようになります。

app [1,2,3]
[1]@(app [2,3])
[1]@([2]@(app [3]))
[1]@([2]@([3]@(app [])))
[1]@([2]@([3]@([])))
[1]@([2]@[3])
[1]@([2,3])
[1,2,3]

これは、関数呼び出しが の左側にあるため@です。

これを単純なバージョンの と比較してくださいrev:

fun rev [] = []
  | rev (x::xs) = rev xs @ [x]

これには期待どおりの実行時間があります。再帰が式に完全に展開されると((([])@[3])@[2])@[1](線形時間かかります)、n + (n - 1) + (n - 2) + ... + 1、または n(n +1)/2、または O(n^2) ステップで計算を完了します。より効果的なものは次のrevようになります。

local
  fun rev' [] ys = ys
    | rev' (x::xs) ys = rev' xs (x::ys)
in
  fun rev xs = rev' xs []
end
于 2012-12-07T22:03:31.953 に答える