O(n)

Phoemuex

Ich habe mal eine Frage:

In Büchern und online lese ich oft etwas wie O(n). Das muss irgendetwas mit der Laufzeit oder so zu tun haben, ich weiß aber nicht, was.
Kann mir das vielleicht jemand sagen?

Schonmal Danke

Felix

O(n) heißt, dass die Laufzeit maximal linear mit der Komplexität des Problems ansteigt.

Das gibt die Komplexitätsklasse (ganz korrekt eigentlich die obere Schranke für die Komplexität) eines Problems oder eines Algorithmus an. n ist dabei die Problemgröße.
Wenn du einen Algorithmus mit der Komplexität O(n) hast, dann bedeutet das, dass der Aufwand einer Berechnung linear mit der Problemgröße wächst. Wenn du 2 Tage brauchst, um eine Liste mit 10 Einträgen zu sortieren, brauchst du dann ungefähr 4 Tage für eine Liste mit 20 Einträgen.
Es gibt aber auch kompliziertere Probleme, die können dann z.B. die Komplexitätsklasse O(n²) haben. Wenn du 4 Tage brauchst, um 2 Eier zu vergleichen, brauchst du dann 16 Tage, wenn du 4 Eier vergleichen willst. Weniger ist also besser, man sieht ja, dass n² größer ist als n. Man nimmt dabei für n fast immer eine ganze Zahl an, meistens eine größere wie hundert oder tausend.

Der Witz bei der Komplexitätsangabe ist, dass es egal ist, wie schnell dein Computer ist. Wenn ich einen Algorithmus habe, der eine Liste in O(n * log n) sortiert, bin ich immer besser als du mit einem Algorithmus mit O(n²), auch wenn dein Rechner doppelt so schnell ist. Wenn das n groß genug ist, zählt die Komplexität viel mehr als andere Faktoren, deshalb ist das oft ein gutes Maß für die Effizienz eines Algorithmus. Man gibt mit dieser Notation oft auch den Speicherbedarf und nicht nur das Laufzeitverhalten an.

SideWinder

Noch ein paar mehr Infos, eventuell wirds ein FAQ-Beitrag.

Gängige Laufzeitklassen mit Namen:

[i]Gut skalierend:[/i]

1          konstant               Einfügen in einen Stack
log(n)     logarithmisch          Suchen in einem Binärbaum

[i]Linear skalierend:[/i]

n          linear                 Sequentielle Suche

[i]Schlecht skalierend:[/i]

n*log(n)   linear-logarithmisch   Ein optimales Sortierverfahren
n²         quadratisch            Bubblesort
2[h]n[/h]         exponentiell           (Jemand ein Beispiel?)

Hier die Angaben, die man bei einem Algorithmus macht:

[e]Theta[/e] - Worst Case (Oftmals gibts nur diese Angabe)
[e]Omega[/e](n) - Best Case
??? - Average Case

Fachbegriffe:
assymptotisch optimal
Wenn für einen Algorithmustyp die bestmögliche Laufzeitklasse die theoretisch möglich ist erreicht wurde handelt es sich um einen asymptotisch optimalen Algorithmus (ZB ein Sortierverfahren mit n*log(n) Laufzeit)

Gibt sicher noch Leute mit mehr Wissen zum Thema, erweitert den Thread ruhig

MfG SideWinder

Die Frage muss irgendwie ein Scherz sein.

borg

SideWinder schrieb:

n*log(n)   linear-logarithmisch   Ein optimales Sortierverfahren

optimal nur bei den vergleichssortierern

SideWinder schrieb:

Hier die Angaben, die man bei einem Algorithmus macht:
[e]Theta[/e] - Worst Case (Oftmals gibts nur diese Angabe)
[e]Omega[/e](n) - Best Case
??? - Average Case

nein, das ist falsch.
O gibt eine obere schranke an, Ω eine untere und Θ ist beides.
angenommen ein algorithmus hat die laufzeit T(n), dann gilt:
$T(n) \in O(g(n)) \Leftrightarrow \exists c,n\_0: \forall n\geq n\_0 : 0 \leq T(n) \leq c\cdot g(n)$
O ist also eine menge von laufzeiten. bei O(n) sind es zB alle die linear ansteigen, also a+bn für a und b beliebig groß.
wenn ein algorithmus nun also O(n) hat, bedeutet dies, der algorithmus hat asymptotisch maximal eine lineare laufzeit. er kann also auch O(1) haben. ein algorithmus der Θ(n) hat, hat asymptotisch eine lineare laufzeit. ein algo der Ω(n) hat, hat mindistens eine lineare laufzeit.
daher ist die untere schranke für vergleichssortierer auch Ω(n*logn) oder Θ(n*logn), aber _nicht_ O(n*logn).

man gibt also mit O, Ω und Θ nicht den average/worst/best-case an. man gibt das T(n) im average/worst/best-case an und schätzt es dann mit O, Ω oder Θ ab.

n*log(n) würde ich nicht gerade als schlecht skalierend bezeichnen. Auch polynomielle Laufzeiten gelten oft noch als "schnell".

Wie gut oder schlecht etwas ist, hängt von der Problemstellung ab. Wenn ich das Problem des Handlungsreisenden in O(n²) lösen könnte, wäre das ziemlich gut.

Optimizer schrieb:

Wie gut oder schlecht etwas ist, hängt von der Problemstellung ab. Wenn ich das Problem des Handlungsreisenden in O(n²) lösen könnte, wäre das ziemlich gut.

Ich kanns in n * log n.

tra schrieb:

Optimizer schrieb:

Wie gut oder schlecht etwas ist, hängt von der Problemstellung ab. Wenn ich das Problem des Handlungsreisenden in O(n²) lösen könnte, wäre das ziemlich gut.

Ich kanns in n * log n.

Aber nicht mit einer DTM.