Programmierung 1 - Repetitorium

WS 2002/2003

Programmierung 1 - Repetitorium

Andreas Augustin und Marc Wagner

Homepage: http://info1.marcwagner.info

Programmierung 1 - Repetitorium

Dienstag, den 08.04.03

Kapitel 4

Laufzeit

Programmierung 1 - Repetitorium

4.1 Vorbemerkungen

Im folgenden betrachten wir das Blackbox-Modell :Die Prozedur ist ein Kasten mit einer Eingabe- und Ausgabeöffnung.Bei erfolgter Eingabe beginnt der Kasten mit der Berechnung.Entweder rechnet der Kasten unendlich lang (Divergenz) oder er legt nacheiner gewissen Zeit das Ergebnis in die Ausgabeöffnung (Terminierung).

Die Laufzeit eines Prozeduraufrufs ist die Zeit bis zur Lieferung desAusgabewertes.

Irrelevant für die theoretische Laufzeit sind die Geschwindigkeit des Computers,die Details der Programmiersprache, die Größenbeschränkung von Zahlensowie die Speicherbeschränkung des Computers.

Wir betrachten die Teilsprache FML, welche ohne Gleitkommazahlen undAusnahmen besteht.

Programmierung 1 - Repetitorium

4.2 Laufzeit und Rekursionsbäume

Die Laufzeit eines terminierenden Prozeduraufrufs A ist die Anzahl aller Aufrufevon rekursiven Prozeduren, die für die Ausführung von A ausgeführt werden müssen. Die Laufzeit einer Prozedur ist die Funktion, die den Argumenten,für die die Prozedur terminiert, die Laufzeit des entschprechenden Aufrufs zuordnet.

Diese Definition der Laufzeit zählt nur die Aufrufe von rekursiven Prozeduren.

Sei A ein terminierender Prozeduraufruf. Spezialfälle sind :

1. Wenn für die Ausführung von A keine rekursive Prozedur aufgerufenwerden muss, dann hat A gemäß unserer Definition die Laufzeit 0.

2. Wenn A der Aufruf einer rekursiven Prozedur ist, die keine anderenrekursiven Prozeduren aufruft, dann ist die Laufzeit von A gleich derGröße des Rekursionsbaums von A.

Programmierung 1 - Repetitorium

4.2 Laufzeit und Rekursionsbäume

Beispiel : Fakultätsfunktion

fun fak n = if n = 0 then 1 else n*fak(n-1)

Man sieht sofort, dass fak für n ℕ terminiert.Der Rekursionsbaum für einen Aufruf fak n ist linear und hat die Tiefe n.Also hat fak für n ℕ die Laufzeit n+1.

Beispiel : Exponentialfunktion

fun ex n = if n < 1 then () else (ex(n-1),ex(n-1))

Für n N ist der Rekursionsbaum für ex n ein balancierter Binärbaum der Tiefe n.Also hat der Rekursionsbaum für ex n die Größe 2n+1-1.

ex 2

ex 1 ex 1

ex 0 ex 0 ex 0 ex 0

Programmierung 1 - Repetitorium

4.2 Laufzeit und Rekursionsbäume

Beispiel : Appendfunktion

fun append (nil, ys) = ys | append (x::xr, ys) = x :: append(xr,ys)

Da das erste Argument bei jedem rekursiven Aufruf kürzer wird, terminiert appendfür alle Argumente. Der Rekursionsbaum für einen Aufruf von append(xs,ys)hat offensichtlich die Tiefe |xs|. Also hat append(xs,ys) die Laufzeit |xs|+1.

Beispiel : Reversierungsfunktion

fun reverse nil = nil | reverse (x::xr) = append(reverse xr,[x])

Man sieht sofort, dass reverse für alle Argumente terminiert.Achtung : Hilfsprozedur append bei der Laufzeitberechnung beachten !

Sei ∇ die Laufzeit von reverse. Offensichtlich gilt für alle x X und xr ℒ(x) :

∇(nil) = 1∇(x::xr) = 1 + (xr) + (|xr|+1) = 2 + (xr) + |xr|∇ ∇

Programmierung 1 - Repetitorium

4.2 Laufzeit und Rekursionsbäume

fun nabla n = if n=0 then 1 else 2 + nabla(n-1) + (n-1)

xs ℒ(x) : ∇(x) = 1/2 |xs|2 + 3/2 |xs| + 1

Beweis :

Sei xs = nil. ∇(xs) = 1 = 1/2 |xs|2 + 3/2 |xs| + 1 Sei xs = x::xr. ∇(xs) = 2 + ∇(xr) + |xr|

= 2 + 1/2 |xr|2 + 3/2 |xr| + 1 + |xr|

= 2 + 1/2 (|xs|-1)2 + 3/2 (|xs|-1) + |xs|

= 1/2 |xs|2 + 3/2 |xs| + 1

∎

Programmierung 1 - Repetitorium

4.3 Die Funktionsklassen O und Theta

Seien f,g ℕ → ℝ. Wir sagen „f dominiert g“ und schreiben g ≼ f genau dann,wenn ∃ n0 ℕ ∃ c ℕ+ ∀ n ≥ n0 : g(n) ≤ c * f(n).

≼ ist reflexiv und transitiv.

Für jede Funktion f ℕ → ℝ definieren wir zwei Funktionsklassen :

O(f) = { g ℕ → ℝ | g ≼ f } (sprich: „O f“)

Ɵ(f) = { g ℕ → ℝ | f ≾ g ⋀ g ≾ f } (sprich: „Theta f“)

Es gilt : Ɵ(f) ⊆ O(f) und O(f) = O(g) ⇔ Ɵ(f) = Ɵ(g)

O(n log n) ⊊ O(na) ⊊ O(nb) falls 1 < a < b

O(na) ⊊ O(bn) ⊊ O(cn) falls 1 < a und 1 < b < c

O(1),Ɵ(log n),Ɵ(n),Ɵ(n log n),Ɵ(n2),Ɵ(n3),Ɵ(2n) sind disjunkt

O(1) ⊊ O(log n) ⊊ O(n) ⊊ O(n log n) ⊊ O(n2) ⊊ O(n3) ⊊ O(2n)

Programmierung 1 - Repetitorium

4.4 Asymptotische Laufzeiten

Wir sagen, dass eine Prozedur p : int → t die Laufzeit Ɵ(f) hat genau dann,wenn es ein n0 und ein g ℕ Ɵ(f) gibt, sodass für alle n ≥ n0 der Aufrufp n die Laufzeit g(n) hat.Entsprechend sagen wir, dass p die Laufzeit O(f) hat genau dann, wenn esein n0 ℕ und ein g O(f) gibt, sodass für alle n ≥ n0 der Aufruf p n dieLaufzeit g(n) hat.

asymptotische Laufzeitangaben : Angaben mit O und Ɵ

exakte Laufzeitangaben : Angaben ohne O und Ɵ

O(1) konstante Laufzeit Ɵ(log n) logarithmische Laufzeit

Ɵ(n) lineare Laufzeit Ɵ(n2) quadratische Laufzeit

Ɵ(n3) kubische Laufzeit Ɵ(an) exponentielle Laufzeit

obere Aufwandsfunktion (Maximum der Laufzeiten, „worst case“)

untere Aufwandsfunktion (Minimum der Laufzeiten, „best case“)

Programmierung 1 - Repetitorium

4.5 Schnelle Exponentiation

fun exp(x,n) = if n=0 then 1 else if n mod 2 = 0 then exp(x*x,n div 2) else x*exp(x*x,n div 2)

Die Terminierung von exp für (x,n) ℤ x ℕ ist offensichtlich.

Behauptung : Für (x,n) ℤ x ℕ hat exp die Laufzeit Ɵ(log n)

Beweis : Sei (x,n) die Laufzeit von exp(x,n) für (x,n) ∇ x .ℤ ℕ

Wir zeigen durch Induktion über n :∀n xℕ ∀ : (x,n) = 2+(if n=0 then -1 else logℤ ∇ ⌊ 2 n )⌋

Sei n=0. Dann (x,n) = 1.∇

Sei n=1. Dann (x,n) = 1 + (x,0) = 2.∇ ∇

Sei n>1. Dann (x,n) = 1 + (x,∇ ∇ ⌊n/2 )⌋

= 3 + log⌊ 2⌊n/2⌋⌋

= 3 + log⌊ 2(n/2)⌋

= 3 + (log⌊ 2 n) - 1⌋

= 2 + log⌊ 2 n⌋∎

Programmierung 1 - Repetitorium

4.6 Größter gemeinsamer Teiler

fun gcd(x,y) = if y=0 then x else gcd(y, x mod y)

Seien x , y ℕ ℕ+ und x mod y ≥ 1. Dann gilt : y mod (x mod y) < y/2

Behauptung : gcd hat für x,y ℕ2 die Laufzeit O(log y).

Beweis : Sei (x,y) die Laufzeit von gcd(x,y) für x,y ∇ .ℕ

Wir zeigen durch Induktion über y :∀x,y : (x,y) ≤ 2 + 2*(if y=0 then 0 else logℕ ∇ 2 y)

Sei y=0 oder y=1. Dann (x,n) ≤ 2.∇

Sei y≥2.

∎

1. x mod y = 0. Dann (x,y) = 2 < 2 + 2*log∇ 2 y.

2. x mod y > 0 und y mod (x mod y) = 0. Dann (x,y) = 3 < 2 + 2*log∇ 2 y.

3. x mod y > 0 und y mod (x mod y) > 0. Dann (x,y) = 1 + (y, x mod y)∇ ∇= 2 + (x mod y, y mod(x mod y))∇≤ 4 + 2*log2(y mod (x mod y))< 4 + 2*log2 y/2 = 2 + 2*log2 y

Programmierung 1 - Repetitorium

4.7 Iterative Rekursion

fun sumi(x,y) = if x=0 then y else sumi(x-1,y+1)

Iterative Rekursion liegt genau dann vor, wenn die rekursiven Anwendungender Prozedur das Ergebnis der Prozedur liefern.

Nicht iterativ-rekursiv : fun sum(x,y)= if x=0 then y else 1+sum(x-1,y)sumi und sum berechnen beide (x,y) x . x+yℕ ℤ

iterative Rekursion = Endrekursion = Iteration

Iterative Rekursionsbäume sind immer linear, haben also genau ein Blatt.Bei nicht-iterativen Prozeduren steigt der Speicherplatzverbrauch mitsteigender Rekursionstiefe an.

Iterative Rekursion kann auch kaskadiert realisiert werden :

fun sumi x y = if x=0 then y else sumi (x-1) (y+1)

Praktische Konsequenzen : foldl ist iterativ, foldr ist nicht iterativ !

Programmierung 1 - Repetitorium

4.8 Einführung von Akkumulatorargumenten

fun fak n = if n=0 then 1 else n*fak(n-1)

iterative Variante :

Beispiel : Fakultätsfunktion

nicht-iterative Variante :

fun faki‘(n,a) = if n=0 then a else faki‘(n-1,n*a)fun faki n = faki‘(n,1)Rekursionsbaum :

faki‘(4,1)

faki‘(3,4)

faki‘(2,3*4)

faki‘(1,2*3*4)

faki‘(0,1*2*3*4)

Programmierung 1 - Repetitorium

4.8 Einführung von Akkumulatorargumenten

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

Beispiel : Reversierungsfunktion

nicht-iterative Variante :

fun revi‘(nil,ys) = ys | revi‘(x::xr,ys) = revi‘(xr,x::ys)fun revi xs = revi‘(xs,nil)Rekursionsbaum : revi‘([1,2,3,4],[])

revi‘([2,3,4],[1])

revi‘([3,4],[2,1])

revi‘([4],[3,2,1])

revi‘([],[4,3,2,1])

Programmierung 1 - Repetitorium

4.8 Einführung von Akkumulatorargumenten

fun fib n = if n<2 then n else fib(n-1) + fib(n-2)

iterative Variante :

Beispiel : Fibonaccifunktion

nicht-iterative Variante :

fun fibi‘(n,a,b) = if n<1 then a else fibi‘(n-1,b,a+b)fun fibi n = fibi‘(n,0,1)

Rekursionsbaum : fibi‘(n, f0, f1)

fibi‘(n-1, f1, f2)

fibi‘(n-2, f2, f3)

fibi‘(0, fn, fn+1)

...