瞭解涉及列表追加的遞歸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函數的運行時（使用@）

回答

相關問題