了解涉及列表追加的递归SML函数的运行时（使用@）

我是算法分析和SML的新手，并且挂上了以下SML函数的平均情况运行时。我会很感激我的想法。了解涉及列表追加的递归SML函数的运行时（使用@）

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

所以在每次递归之后，我们最终会得到一堆单个元素列表（和一个无元素列表）。

[1]@[2]@[3]@[email protected][n]@[]

凡n是在原列表和元素1, 2, 3, ..., n的数量只是为了说明我们正在谈论在原始列表中哪些元素。 L @ R需要时间线性列表L.假设A的长度是@需要为每个元素的时间相同的量，我想这仿佛：

[1,2]@[3]@[4]@[email protected][n]@[] took 1A 
[1,2,3]@[4]@[email protected][n]@[] took 2A 
[1,2,3,4]@[email protected][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）vsΘ（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存在，或者是我的分析（至少在某种程度上）正确的方式真的吗？

来源

2012-11-29 Max

'@'是左操作数列表的大小呈线性关系，但在这里，它总是被称为一个元素列表上。 –

我想我明白了。我按照相反顺序添加列表，即[1] @ [2] @ [3] @ [4] @ ... @ [n] @ []最终会是[1] @ [2,3， ...，N]。这是正确的吗？ – Max

是的，没错。你所执行的每个追加都是恒定的。 –

是的。在同一时间运行手工一个函数调用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-07 22:03:31

谢谢你的回答和点解释，西蒙。我做的（nooby）错误是忽略括号。 – Max

了解涉及列表追加的递归SML函数的运行时（使用@）

回答

相关问题