Landau-Notation ("groß O") - Beispiele (Teil 1 von 2)

Das Wichtigste aus dem Video

Tipp auf eine Zeit – das Video springt genau dorthin.

1. 0:17 Für eine exakte Laufzeitanalyse müssen Addition beziehungsweise Subtraktion, Multiplikation, Vergleiche, Sprünge sowie Speicherzugriffe einzeln berücksichtigt werden. Ihre konkreten Kosten hängen jedoch vom Prozessor, der Maschinensprache und der Übersetzung durch den Compiler ab.
2. 3:02 Selbst eine einfache Zuweisung oder Rechenzeile kann auf Maschinenebene mehrere Operationen umfassen, etwa Lesen, Multiplizieren und Schreiben. Compileroptimierungen wie das Halten von Variablen in Registern können diese Kosten verändern.
3. 5:33 Beim Fakultätsalgorithmus wird der Schleifenkörper \(n\)-mal ausgeführt, während der Schleifentest \(n+1\)-mal erfolgt. Eine detaillierte Rechnung ergibt daher eine lineare Laufzeit; das genaue Zählen ist allerdings fehleranfällig.
4. 6:29 Eine exakte Laufzeitformel gilt nur für das konkrete Programm auf der angenommenen Maschine. Die Landau-Notation abstrahiert diese technischen Details und beschreibt den Fakultätsalgorithmus als \(O(n)\), also mit linearem Laufzeitverhalten.
5. 9:48 Zuweisungen, Vergleiche, Speicherzugriffe und elementare arithmetische Operationen werden im verwendeten Modell jeweils als \(O(1)\) behandelt, weil ihre Dauer nicht von \(n\) abhängt. Unterschiedliche konstante Einzelkosten spielen für die asymptotische Ordnung keine Rolle.
6. 10:37 Die Annahme, eine Multiplikation sei \(O(1)\), gilt nur für Zahlen in der vom Prozessor bereitgestellten festen Darstellung. Bei sehr großen Zahlen kann die Multiplikationsdauer von der Zahlengröße abhängen; passen Ergebnisse nicht mehr in den Speicherbereich, können sie zudem falsch werden.
7. 12:03 Besteht ein \(n\)-mal wiederholter Schleifenkörper nur aus \(O(1)\)-Operationen, kostet die Schleife \(O(n)\cdot O(1)=O(n)\). Ein zusätzlicher konstanter Prolog ändert daran nichts, denn bei \(O(n)+O(1)\) bleibt nur der größere Term \(O(n)\).
8. 13:58 Vor der Landau-Rechnung musst du festlegen, was gemessen wird und welche Operationen als konstant gelten. Diese Modellierungsentscheidung nimmt dir die Notation nicht ab; sie vereinfacht erst anschließend die Rechnung.
9. 14:50 Die geometrische Summe \(q^0+q^1+\dots+q^n\) lässt sich direkt berechnen, indem für jedes \(i\) die Potenz \(q^i\) bestimmt und zur Summe addiert wird. Die gezeigte Potenzfunktion erzeugt \(x^k\), indem sie ein Ergebnis \(k\)-mal mit \(x\) multipliziert.
10. 17:19 Eine effizientere Berechnung der geometrischen Summe führt den jeweils nächsten Summanden mit: Ausgehend von \(1\) wird er nach jeder Addition mit \(q\) multipliziert. So entstehen nacheinander \(1,q,q^2,q^3,\dots\), ohne jede Potenz erneut von vorn auszurechnen.
11. 18:58 Die iterative Potenzfunktion benötigt für \(x^k\) genau \(k\) Schleifendurchläufe mit jeweils konstantem Aufwand. Ihre Laufzeit ist deshalb \(O(k)\).
12. 20:53 Im direkten Summenalgorithmus kostet der Aufruf zur Berechnung von \(q^i\) jeweils \(O(i)\); der Schleifenkörper ist also nicht in jedem Durchlauf gleich teuer. Für eine grobe Worst-Case-Abschätzung kann man \(i\le n\) verwenden und erhält \(n\) Durchläufe mit höchstens \(O(n)\) Aufwand, insgesamt also \(O(n^2)\).
13. 24:12 Genauer erhält man durch Addition der einzelnen Potenzkosten \(c\cdot0+c\cdot1+\dots+c\cdot n=c\cdot n(n+1)/2\). Der quadratische Term dominiert und konstante Faktoren entfallen, sodass ebenfalls \(O(n^2)\) folgt.
14. 27:06 Der optimierte Algorithmus hat lineare Laufzeit \(O(n)\), der direkte Ansatz quadratische Laufzeit \(O(n^2)\). Mit wachsendem \(n\) wird ihr Unterschied deshalb immer größer, während zwei lineare Algorithmen sich trotz verschiedener konstanter Faktoren nicht auf diese Weise auseinanderentwickeln.

Zum Nachlesen