Suche Home Einstellungen Anmelden Hilfe

1.3.1 Laufzeitverhalten und Speicherplatzbedarf

Unter Komplexität eines Programmes versteht man also den Ressourcenverbrauch zur Laufzeit eines Programmes. Nun sind bei Fertigstellung des Programmes einige Dinge noch unbekannt. So weiß man im Allgemeinen nicht, wie leistungsfähig das System sein wird, auf dem das Programm letztendlich läuft. Aber auch die tatsächlichen Eingabewerte kennt man nicht.

Der Rechner wird nicht betrachtet. Bei den Eingabewerten überlegt man sich, wie viel Ressourcen das Programm im besten oder schlechtesten Fall oder im Durchschnitt verbraucht.

best case Ω

Der minimale Ressourcenverbrauch - bei geeigneter Eingabe. Das ist leicht berechenbar, jedoch wenig aussagekräftig, da nicht immer mit der optimalen Eingabe gearbeitet wird und große Unterschiede zwischen best und worst case bestehen können.

worst case O

Der maximale Ressourcenverbrauch - bei ungeeigneter Eingabe. Ebenfalls leicht berechenbar.

average case Θ

Der durchschnittliche Ressourcenverbrauch - gemittelt über alle möglichen Eingaben. Das ideale Maß zur Bemessung, aber schwierig zu berechnen. Warum? Um über alle möglichen Eingaben mitteln zu können, muss die Wahrscheinlichkeit jeder einzelnen Eingabe berücksichtigt werden. Oft kann man diese nicht angeben.

Die Komplexitätsanalyse beschränkt sich meist auf den worst case.

Schätzen Sie die Laufzeit in Abhängigkeit von der Länge des Eingabewortes. Die hypothetischen Programme besitzen dabei Komplexitäten von n, n⁵ und 2ⁿ. Eine Komplexität von n bedeutet, dass bei einer Eingabe der Größe 10 genau 10 Operationen ausgeführt werden. Bei einer Komplexität von n² wären es bereits 10² = 100 Operationen.

Desweiteren nehmen wir an, der Prozessor, der diese Programme bearbeitet, kann 1.000.000 Operationen in der Sekunde ausführen. Wie lange dauert die Ausführung für eine Wortlänge von 10, 20, 40 oder 50?

Laufzeit-\ Wortlänge verhalten\	10	20	40	50
n	0,001 ms 0,01 ms 0,1 ms 1 ms	0,002 ms 0,02 ms 0,2 ms 2 ms	0,04 ms 0,2 ms 0,4 ms 4 ms	5 ms 1 ms 0,5 ms 0,05 ms
n5	0,1 ms 1 ms 12,5 ms 100 ms	2,5 s 3,2 s 6,4 s 12,0 s	64 s 102 s 310 s 480 s	265 s 313 s 422 s ca. 10 min
2n	0,1 ms 1 ms 10 ms 100 ms	0,1 s 1 s 10 s 100 s	ca. 24 h ca. 5 Tage ca. 13 Tage ca. 19 Tage	ca. 64 Tage ca. 320 Tage ca. 5 Jahre ca. 36 Jahre

Hätten Sie es so vermutet? Stellen Sie sich ruhig einmal vor, ein sprachverarbeitendes Programm der Komplexität n⁵ müsste einen 50 Worte umfassenden Text verarbeiten. Eingabe von Compilern, die Programmcode in Maschinensprache übersetzen, sind oft mehrere 1000 Codezeilen lange Programme.
Auf Seite 3 vermittelt Ihnen ein Diagramm einen Überblick über typisches Laufzeitverhalten .

Einführung 1   2   3   4   5 Übersicht

Benutzer: Gast • Besitzer: matthias • Zuletzt geändert am: