Algorithmus Laufzeit Beispiel Essay



Previous: Komplexität und Verifikation Up: Komplexität und Verifikation Next: Korrektheit und Terminierung

O-Notation

Seien f, g : NN

f ist höchstens von der Größenordnung g

in Zeichen: fO(g)

falls n0c   N existieren mit

 n   n0 :  f (n  c  .  g(n) .

Statt fO(g) sagt man auch f = O(g)

Wegen des konstanten Faktors c ist die exakte Festlegung eines Schrittes nicht erforderlich.

Beispiel:

Sei f (n) = 31n + 12n2.

Dann ist fO(n2)

Natürlich gilt auch: fO(n7) Die wesentlichen Klassen

Annahme: 1 Schritt dauert 1 s = 0.000001 s Für einen Algorithmus mit Laufzeit O(2n) gilt daher:
Wächst n um 1, so wächst 2n um den Faktor 2.
Wächst n um 10, so wächst 2n um den Faktor 210 = 1024.
Ein 1000-mal schnellerer Computer kann eine um 10 Daten größere Eingabe in derselben Zeit bearbeiten.
Analoge Aussagen sind möglich bzgl. Speicherplatz.
Wir zählen nicht die Anzahl der Bytes, sondern betrachten das Wachstum des Platzbedarfs in Speicherplätzen in Abhängigkeit von der Größe der Eingabe.

Aussagen über Laufzeit und Platzbedarf beziehen sich auf

best casegünstigster Fall
worst caseungünstigster Fall
average caseim Mittel

Analyse von -Schleifen

Beispiel:

Minimumsuche in einem Array der Länge n

min = a[0]; for (i = 1; i < n; i++){ if(a[i] < min) min = a[i]; }
Laufzeit O(n) fürbest case
 worst case
 average case.
Beispiele: for (i = 0; i < k; i++) { for (i = 0, i < k; i++) { for (j = 0; j < k; j++) { for (j = 0; j < k; j++) { brett[i][j] = 0; if (a[i] == a[j]) treffer = true; } } } }
k2 Schritte für k2 Daten                                 k2 Schritte für k Daten
O(n) -Algorithmus O(n2) -Algorithmus

Analyse von -Schleifen

Beispiel:

Lineare Suche im Array

i = 0; while (i < n) && (a[i] != x) { i++; }

Annahme für den average case:
Es liegt Permutation der Zahlen von 1 bis n vor.
Dann ist die mittlere Anzahl


Beispiel:

Suche 0 in einem Array, bestehend aus Nullen und Einsen.

Obacht:

Alle Laufzeitangaben beziehen sich jeweils auf einen konkreten Algorithmus A (für ein Problem P) = obere Schranke für Problem P.

Eine Aussage darüber, wie viele Schritte jeder Algorithmus für ein Problem P mindestens durchlaufen muss, nennt man untere Schranke für Problem P.

Beispiel: naives Pattern-Matching

char[] s = new char6; // Zeichenkette char[] p = new char[M]; // Pattern

Frage: Taucht Pattern p in Zeichenkette s auf?

for (i = 0; i <= N - M; i++) { // Index in Zeichenkette for (j = 0; (j < M) && (p[j] == s[i+j]); j++); // Index im Pattern if (j == M) break; // Erfolg }
Laufzeit best case:O(1)   
Laufzeit worst case: (N - M + 1) . M Vergleiche fürs=AAA...AB
  p=A...AB

Sei n die Summe der Buchstaben in Pattern p und String s. Sei M = x . n und N = (1 - x) . n für 0 < x < 1.

Gesucht wird x, welches ((1 - x) . n - x . n + 1) . x . n = (n2 + n) . x - 2n2 . x2 maximiert.

Bilde 1. Ableitung nach x und setze auf 0: 0 = n2 + n - 4n2 . x

  1. [ ] Maximum liegt bei    
Also können (n - n + 1) . n = n2 + n Vergleiche entstehen.
  1. [ ] Die Laufzeit im worst case beträgt O(n2).

Analyse eines rekursiven Programms

Beispiel:

Die Laufzeit von fib(n) beträgt:

f (n) =
Offenbar gilt: fO() für ein < 2 (denn f (n) = f (n - 1) + f (n - 1) würde zu O(2n) führen).

Gesucht ist also ein , so dass für große n gilt:

= + + 1

Teile durch :

= + 1 + . Für n und > 1 geht 0.
= + 1 = + = 1.61803 (gemäß Formel - )
Das rekursive Fibonacci-Programm hat die Laufzeit O(1.62n), wobei n der Wert des Inputs ist, nicht seine Länge!
für n = 20 ist1.62n 15.000
 2n 1.000.000.

Unterabschnitte

Previous: Komplexität und Verifikation Up: Komplexität und Verifikation Next: Korrektheit und Terminierung

Ein linearer Algorithmus ist ein Algorithmus dessen Laufzeit linear in der Größe der Eingabe ist. Dies bedeutet, dass der Algorithmus für eine doppelt so große Eingabe in etwa doppelt so lange braucht. Man sagt auch: "Der Algorithmus ist in O(n)".

Lineare Algorithmen werden in der Regel als sehr schnelle Algorithmen angesehen. Sie gehören der Klasse der polynomiellen Algorithmen an.

Beispiel[Bearbeiten | Quelltext bearbeiten]

Für die Aufgabe, die größte Zahl aus einer Liste mit n Einträgen zu finden, gibt es einen linearen Algorithmus:

  1. Setze die erste Zahl der Liste als (vorläufiges) Maximum.
  2. Gehe jetzt die restlichen Zahlen der Reihe nach durch und überprüfe jedes Mal, ob …
    diese Zahl größer ist, als das bisherige Maximum.
    Wenn ja, dann ersetze das (vorläufige) Maximum durch diese Zahl.
  3. Der Algorithmus ist fertig, wenn die letzte Zahl überprüft wurde.

Die Größe der Eingabe ist hier die Anzahl der Zahlen in der Liste. Um die Laufzeit des Algorithmus zu berechnen betrachtet man die Anweisungen der Reihe nach:

  • Die erste Anweisung dauert eine Zeiteinheit.
  • Danach kommt eine Schleife, die n-1 mal durchlaufen wird. In der Schleife werden ein oder zwei Anweisungen ausgeführt, damit bekommt man eine Laufzeit l zwischen n-1 und 2·(n-1) für die Schleife.
  • Nimmt man alles zusammen, so ist die Laufzeit c·(n), mit einer Konstanten c, die zwischen 1 und 2 liegt und die von der konkreten Eingabe abhängt. Um solche Abhängigkeiten zu vermeiden benutzt man die sogenannten Landau-Symbole, und schreibt hierfür kurz O(n).

0 Thoughts to “Algorithmus Laufzeit Beispiel Essay

Leave a comment

L'indirizzo email non verrà pubblicato. I campi obbligatori sono contrassegnati *