GEHNIO |
|
> Home > Algorithmen > Datenstrukturen > Probleme > Highlights > Themen > Mindmaps > Aufgaben > Programmierung > Facharbeit > Abitur > Projekte > Informatik-AG > News > Impressum |
Um die Laufzeit eines Algorithmus zu bestimmen, hat es
sich als nützlich erwiesen, eine Funktion T(n) zu verwenden, um die Anzahl
der Zeiteinheiten zu repräsentieren, die der Algorithmus für eine Eingabe
der Größe n verbraucht. Man sagt dann: T(n) ist O(f(n)) oder T hat die
Ordnung von f (in Zeichen T(n)=(f(n)), Genau genommen ist O(f(n)) eine Menge, nämlich die
Menge aller Funktionen T, die sich nach dem O-Kalkül mit f(n) abschätzen
lassen. Für Algorithmen benutzt man ähnliche Ausdrucksweisen
wie für ihre Laufzeitfunktionen. So sagt man vereinfacht, ein Algorithmus
hat die Ordnung f(n), wenn seine Laufzeitfunktion T(n) von der Ordnung
O(f(n)) ist. Beispiel Angenommen, man hat für einen Algorithmus die
Laufzeitfunktion T8n)=n2+1 bestimmt. Wir können dann sagen,
dass T(n)=O(n2) ist, weil es Konstanten c=4 und n0=1
gibt, so dass für alle n>=n0 gilt : |n2 +1| <=
c* |n2|. Vereinfacht sagt man dann, der Algorithmus ist
von der Ordnung O(n2) oder der Algorithmus verhält sich
quadratisch. Zur Bestimmung der Ordnung einer Funktion sind
die zwei folgenden Regeln hilfreich:
|
© 2001 Gesamtschule Duisburg-Hamborn/Neumühl. |