GEHNIO
Gesamtschule Duisburg-Hamborn/Neumühl
Informatik in der Oberstufe

> Home
> Algorithmen
> Datenstrukturen
> Probleme
> Highlights
> Themen
> Mindmaps
> Aufgaben
> Programmierung
> Facharbeit
> Abitur
> Projekte
> Informatik-AG
> News
> Impressum
> email
 


Die O-Notation


 

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.
Ordnet man jeder Elementaroperation oder jedem Schritt des untersuchten Algorithmus die Zeiteinheit 1 zu, so kann man mit T(n) die Anzahl der notwendigen Operationen in Abhängigkeit von der Größe der Eingabe größenordnungsmäßig abschätzen, wobei grundsätzlich vom ungünstigsten Fall (worst case Komplexität) auszugehen ist. Bei dieser Vorgehensweise spricht man von einem uniformen Komplexitätsmaß. 

Unter Verwendung des O-Kalküls (auch Landau Symbol) kann die Laufzeit eines Algorithmus dann wie folgt exact definiert werden.

Sei T(n) die Laufzeit eines Algorithmus, die als Funktion über der Eingabegröße n berechnet wird, wobei

  1. n eine nichtnegative ganze Zahl ist und
  2. T(n) für alle n nichtnegativ ist.

Man sagt dann:

T(n) ist O(f(n)) oder T hat die Ordnung von f (in Zeichen T(n)=(f(n)),
wenn es Konstenten c und n0 (natürliche Zahlen) gibt, so dass für alle n>=n0 gilt:
|T(n)|<=c*|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.
Alternativ hätte man auch c=3 und n0=2 auswählen können, da sich zeigen läßt, dass n2+1 <= 2n2 für alle n>=3 ist.

Zur Bestimmung der Ordnung einer Funktion sind die zwei folgenden Regeln hilfreich:

  1. Konstante Faktoren sind unwichtig!
    Beispiel: Die Funktionen T(n)=2n3 und S(n)=2n3+14 heben beide die Ordnung O(n3)
  2. Terme niedriger Ordnung sind Unwichtig!
    Beispiel: T(n)=3n5 + 10n4 + n + 3 ist von der Ordnung O(n5).

< /SUP>  

 

 

 

 

 

 

 

 
  © 2001 Gesamtschule Duisburg-Hamborn/Neumühl.  
Hosted by www.Geocities.ws

1