O-Notation oder Komplexitätsklasse

Mit der O-Notation kann man Klassen von Algorithmen erstellen. Im Grunde geht es darum, dass man abschätzen kann, wie sich die Laufzeit eines Algorithmus im Vergleich zu einem anderen Algorithmus verhält. Die Algorithmen erledigen natürlich die gleiche Aufgabe, aber mit unterschiedlichen Herangehensweisen. Zum Beispiel Algorithmus 1 für kleine (kurze) Aufgaben effizienter ist, aber Algorithmus 2 besser für komplexe (lange) Aufgaben. Da man das Laufzeitverhalten eines Algorithmus aber nicht genau vorhersagen kann, teilt man Algorithmen in Klassen ein.
Man kann mit der O-Notation nicht berechnen wie lang ein Algorithmus brauchen wird bis er fertig ist. Vielmehr stellt es eine Vergleichsmöglichkeit von Algorithmen dar – und zwar bezogen auf große Werte ( $n \rightarrow \infty$ ).

f in O(g)

O-Notation

Nehmen wir an, wir hätten 2 Algorithmen g und f. Wie man auf dem Bild rechts erkennen kann, ist der Algorithmus g effizienter, wenn er weniger als $n_0$ mal aufgerufen wird. Nach $n_0$ sollte man allerdings die Algorithmus g vorziehen.
Man kann sagen: “Der Algorithmus f ist in O(g).” Das trifft zu, für alle n > $n_0$ .

“f liegt in groß-O von g.”

f wird auf dauer also der effizientere Algorithmus sein; er arbeitet die gleiche Aufgabe schneller ab (ab n > $n_0$ , aber kleinere Werte werden ignoriert).
Mit dieser O-Notation stellt man also dar, dass f(n) maximal (auch gleich!) so schnell wächst wie g(n). Somit gilt: $f(n) \in O(g(n))$ .

Beispiel:
$f(n) = 100n$
$g(n) = n^2$
so schreibt man abkürzend: $f(n)$ und $g(n^2)$ . f ist also in O(g(n)), wenn auch erst ab einen $n_0 \geq 100$ . Man untersucht das Verhalten wenn n gegen unendlich geht ( $n \rightarrow \infty$ ). Dabei kann man alle konstanten Werte weglassen.

Asymptotische untere Schranke Ω

f(n) wächst mindestens so schnell wie g(n): $f(n) \in \Omega(g(n))$

Asymptotische exakte Schranke Θ

f(n) wächst genauso schnell wie g(n) wenn:
$f(n) \in O(g(n))$ und $f(n) \in \Theta(g(n))$

Veranschaulichung der O-Notation

Wachstumsreihenfolge

$1 < \log n < \sqrt{n} < n < n(\log n)^2 < n^2 < n^x < x^n$

Schlagworte: Algorithmus, Asymptotisch, Funktion, Komplexitätsklasse, Laufzeit, n0, Notation, O, Schranke, Verhalten

Dieser Beitrag wurde vor am Mittwoch, 18. November 2009 um 23:55 Uhr veröffentlicht und unter GdI1 gespeichert. Sie können Kommentare zu diesem Eintrag über den RSS-2.0-Feed verfolgen. Sie können einen Kommentar hinterlassen oder einen Trackback von Ihrer Website hierher setzen.

brianp.de