3.3 Laufzeit von Programmen - swl.htwsaar.de · 55 Laufzeit von Programmen § Allgemeingilt für unsere Berechnung von Zweierpotenzen § für nwerden insgesamt 4n+ 5Befehle abgearbeitet

53

3.3 Laufzeit von Programmen§ Die Laufzeit eines Programmes T(n) messen wir als

die Zahl der Befehle, die für die Eingabe nabgearbeitet werden

§ Betrachten wir unser Programm zur Berechnungvon Zweierpotenzen, so beobachten wir, dass

§ für n = 1 insgesamt 9 Befehle abgearbeitet werden




Informatik 1 / Kapitel 3: RAM als Rechnermodell

54

Berechnen von Zweierpotenzen


INPUT 0

OUTPUT 10: a <- 1

1: i1 <- s[0]2: if i1 = 0 then jump 6

3: a <- a * 24: i1 <- i1 - 1

5: jump 26: s[1] <- a

7: HALT

55

Laufzeit von Programmen§ Allgemein gilt für unsere Berechnung von Zweierpotenzen

§ für n werden insgesamt 4n + 5 Befehle abgearbeitet

§ Dies lässt sich mittels vollständiger Induktionanhand von Tabellen beweisen

§ Aussage: An (d.h. für n werden 4n + 5 Befehle abgearbeitet)

§ Induktionsanfang: Zeige für n = 1 mittels einer Tabelle,dass insgesamt 9 Befehle abgearbeitet werden

§ Induktionsschritt: Zeige für n + 1, dass vier Befehle mehrals für n abgearbeitet werden (d.h. die Schleife bestehend aus den Befehlen 2–5 wird einmal mehr durchlaufen)


56

Schnelleres Berechnen von Zweierpotenzen§ Wir sehen nun, wie man Zweierpotenzen der Form

schneller berechnen kann

§ Berechnen wir 216 mit unserem bisherigem Programm,so werden insgesamt 69 Befehle abgearbeitet


2 (2 l)

57

Schnelleres Berechnen von Zweierpotenzen§ Wir beobachten, dass für 216 gilt

§ Eine schnellere Berechnung ist also möglich,indem wir die Zahl 2 viermal quadrieren(d.h. mit sich selbst multiplizieren)

§ Allgemein können wir 2(2l) schneller berechnen,indem wir die Zahl 2 l-mal quadrieren


216 =

✓⇣�22�2⌘2

◆2

58

Schnelleres Berechnen von Zweierpotenzen§ Die Eingabe l befindet sich in s[0] und die Ausgabe

der Zweierpotenz 2(2l) erfolgt in s[1]


INPUT 0OUTPUT 1

0: a <- 21: i1 <- s[0]

2: if i1 = 0 then jump 73: s[2] <- a

4: a <- a * s[2]5: i1 <- i1 - 1

6: jump 27: s[1] <- a

8: HALT

59

Schnelleres Berechnen von Zweierpotenzen§ Berechnen wir beispielsweise 2128 = 2(27) mit unserem

ursprünglichen Verfahren, so werden 517 Befehleabgearbeitet, wohingegen mit dem schnellerenVerfahren nur 40 Befehle abgearbeitet werden


60

Schnelleres Berechnen von Zweierpotenzen§ Wir können das Verfahren für Potenzen der Form an

mit einer Basis a > 1 und einem Exponenten n ≥ 0verallgemeinern

§ Betrachte hierzu die Binärdarstellung des Exponenten

und stelle die Potenz an dar als


n = (bk . . . b0)2

an = a bk·2k ⇥ a b k�1·2k�1

⇥ . . .⇥ a b0·20

61

Schnelleres Berechnen von Zweierpotenzen

§ Wir können die Potenz an also berechnen, indem wir

§ k-mal quadrieren (um die Faktoren a2i zu berechnen)

§ k-mal multiplizieren (um die Faktoren zu multiplizieren)

§ Insgesamt benötigen wir also 2k Multiplikationen

§ Der Wert k ist die Zahl der (benötigten) Bits in der Binärdarstellung des Exponenten n und es gilt


k = blog2(n)c

62

O-Notation§ In der Informatik sind wir meist nicht an der genauen

Anzahl abgearbeiteter Befehle interessiert, sonderndaran wie sich diese für wachsendes n entwickelt

§ Die O-Notation (auch: Landau-Notation) erlaubt uns, Größenordnungen von Laufzeiten auszudrücken

§ Intuitiv bedeutet 4n + 4 ∊ O(n), dass die Funktionf(n) = 4n + 4 höchstens so schnell wächstwie die Funktion g(n) = cn für einepositive Konstante c ∊ ℝ+


63

O-Notation§ Definition: Für zwei Funktionen f : ℕ → ℝ+ und

g : ℕ → ℝ+ heißt f ∊ O(g(n)), wenn es positiveKonstanten c ∊ ℝ+ und n0 ∊ ℕ gibt, so dassf(n) ≤ c · g(n) für alle n ≥ n0 gilt


64

O-Notation


n0

g(n)f(n)

’ n Ø n0 : c · g(n) Ø f(n)c · g(n)

65

O-Notation§ Beispiel: Betrachten wir die beiden Funktionen f(n) = 4n + 5 und g(n) = n. Wir “raten“ ein c ∊ ℝ+

und bestimmen ein zugehöriges n ≥ n0


4n + 5 Æ 5n … 5 Æ n

66

O-Notation§ Beispiel: Betrachten wir die beiden Funktionenf(n) = 2n2 + 3 und g(n) = n2 und „raten“ c = 3

somit ist z.B. für n0 = 2 unsere Definition erfüllt


2n2 + 3 Æ 3n2 … 3 Æ n2 …Ô

3 Æ n

67

O-Notation§ Beispiel: Betrachten wir die beiden Funktionenf(n) = 3n3 + n2 und g(n) = n3


68

O-Notation

§ Wie die Schreibweise f ∊ O(g(n)), suggeriert, handelt es sich bei einer Laufzeitklasse O(g(n)) umeine Menge von Funktionen

§ Durch Angabe der Laufzeitklasse eines Programmescharakterisieren wir seine Zeitkomplexität

§ Programme können für Eingaben gleicher Größe nunterschiedliche Laufzeit haben; wir betrachtenimmer den schlechtesten Fall (worst case), d.h.die maximale Laufzeit für eine Eingabe einer Größe


69

O-Notation§ Man versucht in der Regel, eine möglichst „enge“

(d.h. kleine) Laufzeitklasse O(g(n)) zu einergegebenen Funktion f(n) anzugeben

§ Beispiel: Auch wenn log n ∊ O(n317) gilt, bevorzugt mandie Angabe der Laufzeitklasse O(log n)


70

Regeln zum Bestimmen von Laufzeitklassen§ Folgende Regeln können angewendet werden,

um für eine Funktion f(n) eine möglichst„enge“ Laufzeitklasse zu bestimmen

§ additive Konstanten a ≥ 0 dürfen entfallen, d.h.

§ konstante Faktoren a ≥ 0 dürfen entfallen, d.h.


f(n) + a œ O(f(n))

c · f(n) œ O(f(n))

71

Regeln zum Bestimmen von Laufzeitklassen§ dominierte Terme dürfen entfallen d.h. können wir die

Funktion f(n) umschreiben als

und gilt für zwei Terme fi (n) ∊ O(fj (n)),so kann der Term fi (n) entfallen


f(n) = f1(n) + f2(n) + . . . + fk(n)

72

Wachstum von Funktionen


73

Wachstum von Funktionen


f(n) 1 5 10 25log n 0.00 1.61 2.30 3.22n 1.00 5.00 10.00 25.00n log n 0.00 8.05 23.03 80.47n2 1.00 25.00 100.00 625.00n3 1.00 125.00 1, 000.00 15, 625.00en 2.72 14.85 22, 026.47 7, 200, 489, 930.00

74

Wachstum von Funktionen§ Wie können wir allgemein feststellen, ob die Funktion f(n)

schneller wächst als die Funktion g(n)?

§ Betrachte, ob für den Grenzwert des Quotienten gilt

§ Beispiel: Betrachte f(n) = n log n und g(n) = n


limnæŒ

f(n)g(n) æ Œ

limnæŒ

n log n

n= lim

næŒlog n æ Œ

75

Beispiele zum Bestimmen von Laufzeitklassen§ Beispiel: Bestimme möglichst „enge“ Laufzeitklasse für

§ 3n4 + 2n3 + 2n2

§ 3n2 + 12n + log n


76

Beispiele zum Bestimmen von Laufzeitklassen§ n log n + 12 n

§ 13n + log n + 242


77

Beispiele zum Bestimmen von Laufzeitklassen§ log17 n ∊ O(log n)

Hinweis: Logarithmen zu unterschiedlicher Basenunterscheiden sich nur um einen konstanten Faktor


78

Platzkomplexität§ Analog zur Zeitkomplexität eines Programmes können

wir Angaben zu seiner Platzkomplexität machen,d.h. wie viele Speicherstellen S(n) es in Abhängigkeitvon der Eingabe n benötigt

§ Die von uns bisher betrachteten RAM-Programmehaben alle konstante Platzkomplexität in O(1),da die Zahl der benötigten Speicherstellennicht von der Eingabe n abhängt


79

Wann ist ein RAM-Programm effizient?§ Ein RAM-Programm heißt effizient, wenn seine Laufzeit

ein Polynom ist, d.h. T(n) ∊ O(nk) für festes k gilt

§ Unser Programm zur schnelleren Berechnung von Zweierpotenzen hat logarithmische Laufzeit in O(log n)

§ Alle Belegungen von n verfügbaren Bits aufzuzählen,hat exponentielle Laufzeit in O(2n),da es 2n mögliche Belegungen gibt


80

Zusammenfassung§ Schnellere Berechnung von Zweierpotenzen

durch wiederholtes Quadrieren

§ Laufzeiten von Programmen werden durchAngabe einer möglichst „engen“ Laufzeitklassegemäß der O-Notation charakterisiert

§ Regeln zum Bestimmen „enger“ Laufzeitklassen


81

Literatur

[1] H.-P. Gumm und M. Sommer: Einführung in die Informatik, Oldenbourg Verlag, 2012 (Kapitel 4.1.5)

[2] T. H. Cormen, C. E. Leiserson, R. Rivest und

C. Stein: Algorithmen – Eine Einführung,Oldenbourg Verlag, 2009 (Kapitel 3)


Documents

3.3 Laufzeit von Programmen - swl.htwsaar.de · 55 Laufzeit von Programmen § Allgemeingilt für unsere Berechnung von Zweierpotenzen § für nwerden insgesamt 4n+ 5Befehle abgearbeitet