View
232
Download
0
Category
Preview:
Citation preview
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
§ für n = 2 insgesamt 13 Befehle abgearbeitet werden
§ für n = 3 insgesamt 17 Befehle abgearbeitet werden
§ für n = 4 insgesamt 21 Befehle abgearbeitet werden
Informatik 1 / Kapitel 3: RAM als Rechnermodell
54
Berechnen von Zweierpotenzen
Informatik 1 / Kapitel 3: RAM als Rechnermodell
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)
Informatik 1 / Kapitel 3: RAM als Rechnermodell
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
Informatik 1 / Kapitel 3: RAM als Rechnermodell
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
Informatik 1 / Kapitel 3: RAM als Rechnermodell
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]
Informatik 1 / Kapitel 3: RAM als Rechnermodell
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
Informatik 1 / Kapitel 3: RAM als Rechnermodell
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
Informatik 1 / Kapitel 3: RAM als Rechnermodell
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
Informatik 1 / Kapitel 3: RAM als Rechnermodell
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 ∊ ℝ+
Informatik 1 / Kapitel 3: RAM als Rechnermodell
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
Informatik 1 / Kapitel 3: RAM als Rechnermodell
64
O-Notation
Informatik 1 / Kapitel 3: RAM als Rechnermodell
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
Informatik 1 / Kapitel 3: RAM als Rechnermodell
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
Informatik 1 / Kapitel 3: RAM als Rechnermodell
2n2 + 3 Æ 3n2 … 3 Æ n2 …Ô
3 Æ n
67
O-Notation§ Beispiel: Betrachten wir die beiden Funktionenf(n) = 3n3 + n2 und g(n) = n3
Informatik 1 / Kapitel 3: RAM als Rechnermodell
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
Informatik 1 / Kapitel 3: RAM als Rechnermodell
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)
Informatik 1 / Kapitel 3: RAM als Rechnermodell
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.
Informatik 1 / Kapitel 3: RAM als Rechnermodell
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
Informatik 1 / Kapitel 3: RAM als Rechnermodell
f(n) = f1(n) + f2(n) + . . . + fk(n)
72
Wachstum von Funktionen
Informatik 1 / Kapitel 3: RAM als Rechnermodell
73
Wachstum von Funktionen
Informatik 1 / Kapitel 3: RAM als Rechnermodell
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
Informatik 1 / Kapitel 3: RAM als Rechnermodell
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
Informatik 1 / Kapitel 3: RAM als Rechnermodell
76
Beispiele zum Bestimmen von Laufzeitklassen§ n log n + 12 n
§ 13n + log n + 242
Informatik 1 / Kapitel 3: RAM als Rechnermodell
77
Beispiele zum Bestimmen von Laufzeitklassen§ log17 n ∊ O(log n)
Hinweis: Logarithmen zu unterschiedlicher Basenunterscheiden sich nur um einen konstanten Faktor
Informatik 1 / Kapitel 3: RAM als Rechnermodell
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
Informatik 1 / Kapitel 3: RAM als Rechnermodell
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
Informatik 1 / Kapitel 3: RAM als Rechnermodell
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
Informatik 1 / Kapitel 3: RAM als Rechnermodell
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)
Informatik 1 / Kapitel 3: RAM als Rechnermodell
Recommended