[ Inhalt ] [ Index ]

Die Groß-O-Notation

   

In den Algorithmen und Datenstrukturen haben Sie sich bereits mit der Effizienz von Algorithmen beschäftigt. Zur Erinnerung

Definition: (Groß-O-Notation)

Für große n wird das Verhalten von f(n) also durch g(n) bestimmt.

Diese Notation wurde verwendet, um obere Schranken für die Komplexität von Algorithmen anzugeben. Wir erinnern uns an einige Eigenschaften:

O(f+g) = O(f) + O(g) = O(max(f,g))

Beispiele:

Sequentielle Suche   O(n) Binäre Suche   Quicksort   Multiplikation   von 2 n-stelligen Zahlen Matrixmultiplikation   Travelling Salesman  

Angenommen ein Algorithmus benötigt Sekunden für eine Operation. Dann ergibt sich folgende Übersicht:

n 0(n)

10 0.000003 sec 0.00001 sec 0.0001 sec 0.001 sec

100 0.000007 sec 0.0001 sec 0.01 sec

1000 0.00001 sec 0.001 sec 1.0 sec astronomisch

10000 0.000013 sec 0.01 sec 1.7 min ''

100000 0.000017 sec 0.1 sec 2.8 h ''

Dabei setzen wir sec.

Man sieht, daß die Rechenzeit bei Algorithmen aus nahezu explodiert, während sie sich bei den anderen Schranken noch in Grenzen hält.

Der Zeitbedarf   eines Algorithmus f kennzeichnet das Zeitverhalten von f(n) für n Eingaben.

Die Komplexität   eines Algorithmus mit einem Zeitbedarf f(n) heißt

• polynomial  , wenn
• exponentiell  , wenn

Algorithmen mit polynomialem Verhalten sind oft durchführbar, während exponentielle Algorithmen nur für sehr kleine Eingabemengen durchführbar sind. Leider führen aber gerade wichtige Planungsprobleme zu exponentiellen Algoithmen.

Im nächsten Abschnitt sehen wir uns ein wichtiges Problem an, für das kein Algorithmus bekannt ist, der in polynomialer Zeit arbeitet.