# Big-O Notation - (27.11.2024) Wenn wir einen Algorithmus entwerfen, ist unser erstes Ziel auf das richtige Ergebnis zu kommen. Sobald jedoch Leistung ein Faktor wird, muss wohl oder über über die Komplexität nachgedacht werden. Einer der verbreitetsten Wege um die Komplexität darzustellen, ist die Big-O Notation. ## Was ist ein Algorithmus Bevor wir über Big-O sprechen können, ist es wichtig die Definition von Algorithmus in diesem Kontext zu verstehen. Ein Algorithmus kann als Rezept für den Computer zusammengefasst werden. Wir definieren eine reihe von Schritten welche der Computer durchgehen kann, um ein Problem zu lösen. Es ist auch wichtig hinzuzufügen, dass ein Algorithmus hier immer einen Input nimmt und daraus einen Output generiert. Dieser Output muss bei jedem Durchgang mit dem gleichen Input identisch sein, Zufälligkeiten dürfen keine vorkommen. Mit einem Input versuche ich nicht, unseren Algorithmus auf einen Parameter zu beschränken. Es muss mindestens ein Parameter bestehen, ein Algorithmus kann jedoch auch mit mehreren Parametern bestehen. Angenommen wir haben eine Liste `nums` und wir wollen daraus die Summe berechnen: Ein solches Problem kann mit einem Algorithmus gelöst werden. Ein Beispiel für eine Lösung könnte folgendermassen aussehen: 1. Erstelle eine Variabel `sum` mit dem Startwert 0. 2. Iteriere über alle zahlen in `nums`. 3. Zählt die Zahl zu `sum` hinzu. 4. Gib `sum` zurück. Wir haben also eine Reihe von Schritten welche mit einem Input immer auf den richtigen Output kommt: Das nennen wir in diesem Blog einen Algorithmus. ## Big-O Big-O ist eine Notation welche uns ermöglich die Rechenkomplexität (*Computational Complexity*) eines Algorithmus zu beschreiben. Die Rechenkomplexität unterteilen wir in zwei Aspekte: Zeit Komplexität und Speicher Komplexität. Die Zeit Komplexität beschreibt die Dauer die ein Algorithmus relativ zu dessen Input brauch, um das Ergebnis zu berechnen. Die Speicher Komplexität wiederum beschreibt die Menge an Speicher welche relativ zur Inputgrösse benötigt wird. Komplexitäten werden mit Mathematischen Funktionen beschrieben. Die Argumente für diese Funktion sind grundsätzlich vom Entwickler frei wählbar. Die Idee ist jedoch, dass ein expressiver Wert gewählt wird welcher die Unterschiede verschiedener Inputs repräsentiert. In unserem Beispiel von Oben wäre es nicht sinnvoll die durchschnittliche Grösse der Werte zu nehmen, da verschiedene Werte keinen grossen Unterschied auf die Komplexität haben. Stattdessen sollte die Länge der Liste genommen werden: Für jede weitere Zahl in der Liste muss ein weiterer Durchlauf gemacht werden. Die Länge repräsentiert die Unterschiede der Inputs also am besten. Der Variabel-Name welcher für diesen Wert gewählt wird ist irrelevant. Etabliert hat sich der Buchstabe **n**, es obliegt jedoch dem Entwickler ihn zu wählen. Die Funktion wird anschliessend mit einem Grossen **O** (daher auch der Name) umfasst: - *O(n)* - *O(n²)* - *O(log(n))* Wir sind auch nicht auf einen einzelnen Wert begrenzt. Es kann durchaus sein, dass verschiedene Werte einen Einfluss auf die Komplexität haben. In einem solchen Fall können wir so viele Werte in unsere Funktion nehmen, wie wir wollen: - *O(n * m)* Das O wurde von einem der Erfinder gewählt und steht für *Ordnung*.[^2] ## Komplexität berechnen Grob gesagt sollte unsere Funktion die Anzahl an Operationen und Speicher welche relativ zur Input Grösse benötigt werden berechnen. In unserem Beispiel von oben haben wir also eine Zeit Komplexität von *O(n)*. Der Algorithmus iteriert über jeden Eintrag in `nums`, wir definieren *n* also als die Länge von `nums`: Unser Algorithmus sollte ungefähr eine `n`-Anzahl von Schritten benötigen. Wenn `nums` beispielsweise `10` Zahlen enthält, würde unser Algorithmus auch etwa 10 Schritte brauchen, um das Ergebnis zu berechnen. Zeit Komplexität muss nicht absolut genau sein. Stattdessen sollte sie uns ermöglichen, unseren Code zu analysieren, vergleichen und verbesserungswürdige Komponenten zu verbessern. ### Regeln Es gibt einige Regeln zu beachten, wenn wir die Komplexität mit Big-O berechnen wollen: #### Konstanten werden ignoriert Die Komplexität sollte nicht die genaue Anzahl an Operationen berechnen. Was uns interessiert ist die Veränderung relativ zum Input. Es gilt also *O(123n)* = *O(2n)* = *O(n/5)* = *O(n)*. Alle diese Beispiele sind Linear, die Konstante Verschiebung ist für die Analyse des Algorithmus nicht von Bedeutung. #### Nur der grösste Ausdruck zählt Wenn wir mehre Ausdrücke mit der gleichen Variabel haben welche subtrahiert oder addiert werden, interessiert uns nur der grösste Ausdruck. Angenommen unsere Komplexität kommt zu *O(100n - n² + 2ⁿ)*: Auswerten würden wird es zu *O(2ⁿ)*, da *2ⁿ* irgendwann so gross wird, dass die anderen Ausdrücke keinen bemerkenswerten Unterschied mehr machen. Um die einzelnen Ausdrücke auszuwerten schauen wir uns *n* mit einem Wert an, welcher immer weiter in die Unendlichkeit kommt. ### Konstante Zeit Die bestmögliche Komplexität ist *O(1)*. Ein solcher Algorithmus würde unabhängig von der Input Grösse immer die gleiche Anzahl an Operationen nutzen. Diese Komplexität nennen wir Konstante Zeit (*constant time*). Eine gute Komplexität gibt uns keine Informationen über die Geschwindigkeit des Algorithmus, wir wollen aber auch nicht die Geschwindigkeit sondern die Komplexität analysieren. So würden wir auch *O(9999999)* als *O(1)* ausdrücken.[^1][^3] ## Graphische Darstellung Da wir in Big-O mit mathematischen Funktionen arbeiten, können wir unsere Komplexität einfach auch graphisch darstellen. Ein solcher Graph kann dabei helfen, die Unterschiede verschiedener Komplexitäten zu verstehen. ![[complexity.jpg]] *Bild 1: Eine graphische Darstellung der wichtigsten Komplexitäten ([Quelle](https://en.algorithmica.org/hpc/complexity/img/complexity.jpg))* ## Fazit Big-O ist eine einfache Möglichkeit um unsere Algorithmen auf ihre Komplexität zu analysieren. Bezüglich der effektiven Laufdauer gewinnen wir wenig Einblick, ist mit dieser Notation aber auch nicht unser Ziel. Stattdessen erhalten wir Informationen welche uns bei der Optimierung helfen können. [^1]: vgl. Introduction to big O, in: Data Structures and Algorithms, 27.11.2024, https://leetcode.com/explore/interview/card/leetcodes-interview-crash-course-data-structures-and-algorithms/715/introduction/4654/ [^2]: vgl. Big O notation, in: Wikipedia, 27.11.2024, https://en.wikipedia.org/wiki/Big_O_notation [^3]: vgl. Complexity Models, in: Algorithmica - Algorithms for Modern Hardware, 27.11.2024, https://en.algorithmica.org/hpc/complexity/