1

我是算法分析和 SML 的新手，并且被以下 SML 函数的平均情况运行时挂断了。我会很感激一些关于我的想法的反馈。

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

因此，在每次递归之后，我们都会得到一堆单元素列表（和一个无元素列表）。

[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)

WhereC只是基本情况的最终匹配，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需要恒定时间而不是线性时间吗？例如，加法是真的

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

是的。手动运行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 回答