Was ist eine Big O Notation?
Dieser Guide gibt Dir eine Einführung in das Thema.
Starten wir!
Was ist die Big O Notation?
Die Big O Notation gibt an, wie lange ein Computer braucht, um einen Algorithmus auf n Datensätzen auszuführen. Die Notation gibt die Güte eines Algorithmus aus Sicht der Performance an, um Algorithmen besser miteinander zu vergleichen.
Der Informatiker kann nicht immer eine eindeutige Big O angeben, weil der Informatiker die Daten nicht kennt. Statt einem Big O, gibt der Informatiker 3 Big Os an:
- den besten Fall, wenn z. B. der Datensatz vorsortiert ist und der Sortieralgorithmus nichts mehr ändern muss
- den schlechtesten Fall (maximale Rechenzeit) z. B. der Datensatz ist absteigend sortiert, obwohl eine aufsteigende Sortierung gewünscht ist.
- die gewöhnliche Laufzeit hinzu, die in den meisten Fällen bei “gemischten Datensätzen der Realität“ zu erwarten ist.
Big O berechnen
Big O ist keine Zahl / Zeit, sondern eine Formel. Du misst nicht die Sekunden, sondern machst die Laufzeit von den Eingabemengen und Listengrößen abhängig.
Der Informatiker geht davon aus, dass einfache Operationen vom Code eine Laufzeit von 0 haben. Der Computer kann jeden einzelnen Befehl (Lesen, Schreiben, Ändern von Variablen) in einer zu vernachlässigenden Zeit erledigen. Die Realität ist eine andere, aber mit jedem Jahr entwickeln die Prozessorhersteller neuen CPUs, die die Bearbeitungszeit eines einzelnen Schritts verkürzen.
Hiervor ausgenommen sind Operationen auf Listen.
var x = 1 +1; 0(n) = 0
var y = x; 0(n) = 0
var x = 1 +1;var y = x; 0(n) = 0
Grundlagen der Notation
Die Schleifenköpfe sind für die Big O Notation relevant, aber nicht der Schleifenrumpf mit einfachen 1000+ Befehlen.
for(int i =0 ; i < k; i++){
.. irrelevante Statements ...
}
Das Big O von diesem Code ist O(n) = k. Wie Du vielleicht in der 7. Klasse gelernt hast, ist f(x)=k eine lineare Funktion. Die Informatiker sprechen von einer linear skalierenden Algorithmus.
for(int i =0 ; i < k; i++){
}
for(int i =0 ; i < g; i++){
}
Diese ist immer noch linear 0(n) = k + n
for(int i =0 ; i < k; i++){
for(int i =0 ; i < k; i++){
}
}
Komplexere Konstrukte
Diese Funktion ist eine quadratisch skalierende mit 0(n)=k*k. Der Sortieralgorithmus Bubble Sort skaliert mit dieser Funktion.
for(int i =0 ; i < k; i++){
if(unbekannteFunktion(i){
for(int i =0 ; i < k; i++){
}
}
}
Diese Funktion ist tricky. Der Informatiker kann keine genaue Angabe machen, schätzt aber, dass diese im besten Fall O(n)=k ist oder im schlechtesten Fall O(n)=k*k.
Einfache Vorgehensweise für die Praxis
Solltest Du Big O bestimmen, multiplizierst Du die verschachtelte Schleifenvariablen, addierst Du Schleifen, die untereinander stehen, und streichst alle einfachen Befehle weg.
Eine if-Bedingung kann einen Schleifendurchlauf frühzeitig abbrechen lassen, sodass Du einen Bereich wie 1 bis n oder im Durchschnitt log(n) angeben musst.
Die Schleifen
- while
- for
- foreach
- do-while
… sind gleich zu behandeln. Beachte nur, von welchem Startpunkt aus die Schleife zählt und wann diese endet.
Bekannte Algorithmen untersuchen und vergleichen
In der Uni lernst Du die Big O Notation als ein Mittel, um wie Sortieralgorithmen (Bubble Sort, Quick Sort) oder Suchalgorithmen (B*/+-Bäume) zu vergleichen.
Die einfachsten Algorithmen sind in der Regel nicht die performantesten. Ein Bubble Sort skaliert mit n*n schlechter als ein Merge oder Quick Sort.
Eine vollständige Übersicht mit der Angabe zum besten, durchschnittlichen und schlechtesten Big O findest Du in dieser Tabelle.
Die Gefahr – nicht polynominelle Laufzeit
Ein Teilgebiet der Informatik (Komplexitätstheorie) befasst sich mit verschiedenen Algorithmen und ihrer Laufzeit. Ein Typ von Herausforderungen nennt sich NP-Probleme, Algorithmen mit nicht polynominelle Laufzeit.
Die NP-Probleme skalieren z. B. mit 2 hoch n, sodass eine Berechnung schon mit einem „mittleren“ Datensatz einen Supercomputer zum Schwitzen bringt.
Eine Rundreisen– oder Routenplanung gehört zu den NP-Problemen. Bei kleinen Karten kann der Computer alle Routen durchtesten und die kürzeste bestimmen. Größeren Karten weisen sehr sehr sehr viele Routen auf. Der Computer betrachtet jeden Umweg als eine potenzielle Route, die ein Mensch sofort aussortieren würde.
Nur mit Tricks und Hilfestellungen (Heuristiken) kann der Computer eine „sehr gute“, aber nicht immer die optimale Route berechnen.
Praxis – Anwendung von Big O
Wozu den ganze O(n) Kram? Ist das ein weiteres Kapitel Informatik, was Du nach der Prüfung vergessen solltest?
Gefahren, wenn O(n) übergangen wird
Wenn Du das Gesetz der großen Zahlen gekonnt ignorierst, dann entwickelst Du eine Software, die wunderbar mit Deinem kleinen Datensatz auf Deinem lokalen Rechner performant arbeitet. Der Server in der Produktion raucht nach dem ersten größeren Datensatz.
Schachtelst Du ein paar Schleifen ineinander, braucht Dein lokaler Computer mit einem kleinen Datensatz kaum Rechenzeit. Führst Du aber den Code mit der hundertfachen Menge an Daten aus, kann sich die Rechenzeit exponieren.
Ein falsch gewählter regulärer Ausdruck kann den Server zum Schwitzen bringen. (a+)+ mit aaaaaaa! Als Eingabe kann sich toxisch auf die Laufzeit auswirken.
Was ist die Capture Gruppe von (a+)+ und was nicht! Wie kann ein Hacker den Server lahmlegen?
Die Operation kann nach langer Zeit immer noch nicht fertig sein.
Chancen, wenn O(n) optimiert
Wenn Du keinen Code geschrieben hast, der „böse“ Verschachtelungen beinhaltet, sind Optimierungen angebracht, wo Du riesige Datenmengen bewegt werden sollen. In der Praxis sieht die Optimierung so aus, dass Du…
- in einer Schleife eine Abbruchbedingung einbaust.
- Regex Kommandos auf Dopplungen überprüfst.
- erst filtern, dann sortieren.
- Operationen auf die Datenbank auslagerst.
- die Datenmenge begrenzen.
- eine Pagination für einen API-Call verwendest.
- Views / Materialized Views baust.
- Vermeide unnötiges sortieren
- Vermeide unnötige Iterationen oder doppelte Ausführung von Funktionen.
- Speichere Daten zwischen, anstatt diese wieder neu zu berechnen.
Datenmengen bändigen mit einem Cluster
Bei sehr großen Datensätzen kommst Du nicht um einen Map-Reduce Algorithmus herum.
Dein Programm ist optimiert, aber nicht für einen Cluster geeignet. Ein Cluster besteht aus mehreren einzelnen Computern (Nodes), die parallel einen Teil Deines Programms ausführen. Andere Nodes summieren, zählen, sortieren und fassen die Inhalte zusammen.
Für ein solches Programm musst Du im Map-Schritt eine Vorverarbeitung (z. B. Eintrag mit dem Wort „geheim“ herausfinden) vornehmen, die Du auf Basis eines Teildatensatzes erstellen kannst. Der Reduce-Schritt nimmt die gefundenen Dokumente, filtert diese und zählt die Dokumente.
Zeitverlust bei Überoptimierung
Optimiere nur, wenn Du optimieren musst!
Eine Optimierung Deiner Software ist nur notwendig, wenn sich Kunden über lange Wartezeiten beklagen oder alte Computer überfordert sind.
Große Unternehmen, die Big Data in Wissen umwandeln, profitieren von den kleinsten Optimierungen im Code. Diese können Stunden an Berechnungszeit sparen.
Bei einer kleinen Anwendung solltest Du nur bedingt mit Optimierungen Deine Zeit verschwenden. Ein Proof-Of-Concept oder ein Frontend im Browser brauchen nicht diese Optimierungen.
