Laufzeit linear O(n)
Operationsanzahl bei linearer Komplexität: Ops = n · k. Jedes Element wird mit konstantem Aufwand k bearbeitet.
Laufzeit linear O(n) berechnen
Operationsanzahl bei linearer Komplexität: Ops = n · k. Jedes Element wird mit konstantem Aufwand k bearbeitet.
- Ops — Operationen
- n — Eingabegröße
- k — Konstante
Worum geht es?
Eine lineare Laufzeit O(n) liegt vor, wenn die Operationsanzahl proportional zur Eingabegröße n wächst. Das ist der Klassiker einer einfachen Schleife, die jedes Element genau einmal anfasst.
Pro Element fällt ein konstanter Aufwand k an — zum Beispiel ein Vergleich, eine Addition oder ein Funktionsaufruf.
Die Formel
Ops = n · k
Umstellungen:
n = Ops / k
k = Ops / nDie Variablen
| Symbol | Bedeutung | Einheit | Erklärung |
|---|---|---|---|
| n | Eingabegröße | — | Anzahl Elemente in der Eingabe. |
| k | Konstante | — | Aufwand pro Element (Vergleiche, Adds). |
| Ops | Operationen | Ops | Gesamtanzahl Operationen. |
Minimal-Beispiel
Eine Schleife über 10 000 Elemente, pro Element 3 Vergleiche:
Ops = 10 000 · 3
= 30 000 OpsPraxis-Beispiele
Beispiel 1 — Maximum suchen
Lineare Suche nach dem Maximum in einem Array mit n = 1 000 000 Einträgen (k = 1 Vergleich pro Element):
Ops = 1 000 000 · 1
= 1 000 000 VergleicheBeispiel 2 — Konstante k bestimmen
Ein Profiler meldet 4,5 Mio. Operationen für n = 500 000 Elemente:
k = Ops / n
= 4 500 000 / 500 000
= 9 Operationen pro ElementBeispiel 3 — Tragfähige Eingabegröße
Wie viele Elemente n kann ein Algorithmus mit k = 5 in einem Budget von 10⁸ Operationen verarbeiten?
n = Ops / k
= 10⁸ / 5
= 20 000 000 Elemente