목록 추가 (@ 사용)를 포함한 재귀 SML 함수의 런타임 이해

Question

알고리즘 분석과 SML을 처음 사용하고 다음 SML 함수의 평균 사례 런타임에서 중단되었습니다. 내 사고에 대한 의견을 보내 주시면 감사하겠습니다.

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

따라서 모든 재귀 이후에 단일 요소 목록 (및 요소가없는 목록)이 여러 개 있습니다. n 원래 목록의 요소와 1, 2, 3, ..., 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 

그러므로 나는 생각하고 그 시간 동안 재발 것 C베이스 케이스 app([]) 및 B 단지 최종 일치입니다

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

이 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이 존재하거나 내 분석 (적어도 종류의) 올바른 방식을 오해하고 있습니까에도 연결에 대한 사실 것입니까?

Answer 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