Die Komplexität beschreibt die Effizienz eines Algorithmus. Sie gibt in der Groß-O-Notation an, wie der Aufwand eines Algorithmus steigt, wenn die Problemgröße wächst, also die Menge der Eingabedaten zunimmt. Sie wird meist für den besten, durchschnittlichen und schlechtesten Fall bestimmt.
In einem Koordinatensystem wird die Komplexität eines Algorithmus als Funktion der Eingabegröße dargestellt. Auf der horizontalen x-Achse wird die Eingabegröße n und auf der vertikalen y-Achse der entsprechende Funktionswert f(n) dargestellt.
| Beispiel |
| Ein Algorithmus mit der Funktion f(n) = 2 · n berechnet das Doppelte der Eingabegröße. Er hat eine lineare Komplexität O(n), da sein Aufwand proportional zur Eingabegröße n wächst. |
Der Aufwand von Algorithmen (Speicherplatz- und Laufzeit)
Der Aufwand eines Algorithmus wird durch seinen Speicherplatzbedarf und die Anzahl seiner Berechnungsschritte (Laufzeit) ermittelt. Da die meisten Computer einen begrenzten Arbeitsspeicher (RAM) haben, sind gute Algorithmen schnell (geringe Laufzeit) und speichereffizient. Je nach Anwendung optimiert man in der Praxis entweder die Geschwindigkeit oder den Speicherverbrauch.
Bei der Analyse des Aufwands werden alle Anweisungen des Algorithmus (Funktion) ab einer gewissen Mindest-Eingabegröße betrachtet und asymptotisch abgeschätzt. Dabei wir nur der Term mit dem höchsten Wachstum betrachtet.
| Beispiel |
| Ein Algorithmus mit der Funktion f(n) = √n + n3 + 5 eine kubische Laufzeitkomplexität von O(n3), da der Term n3 das höchste asymptotische Wachstum hat. Der konstante Faktor +5 und der niedrigere Ordnungsterm √n werden ignoriert. |
Speicherplatzanalyse (Speicherplatzkomplexität)
Die Speicherplatzkomplexität (Space Complexity) gibt an, wie viel zusätzlicher Speicherplatz ein Algorithmus benötigt, um Eingabedaten und Zwischenergebnisse während seiner Ausführung zu speichern. Der Speicherplatz des Algorithmus selbst zählt nicht dazu. Bei der Codeanalyse wird der Speicher für Variablen, Datenstrukturen und Funktionsaufrufe ermittelt. Bei einem Algorithmus (Funktion) der eine Liste erstellt, wächst der zusätzliche Speicher für das Array linear (O(n)), d.h. proportional mit der Länge der Liste. Auch der Speicherbedarf rekursiver Algorithmen wächst linear, da die Variablen bei jedem rekursiven Aufruf im Stack-Speicher abgelegt werden. Ein logarithmischer Algorithmus (O(log n)) verbraucht weniger Speicher, da er die Problemgröße in jedem Schritt reduziert. Zum Beispiel wird die Eingabegröße bei der binären Suche halbiert. Algorithmen zum Erstellen einer Matrix haben einen quadratischen Speicherzuwachs (O(n2)). Bei einem Würfel (3D-Array) wächst er Kubisch (O(n3)).
| Beispiel |
*** Pseudocode Summe *** Funktion summe(a, b) return a + b Der Algorithmus berechnet die Summe von zwei Zahlen und für die Variablen a und b. Seine Speicherplatzkomplexität ist konstant O(1). |
Beispiele für Speicherplatzkomplexitäten
Laufzeitanalyse (Laufzeitkomplexität)
Im Gegensatz zur Speicherplatzkomplexität gibt die Laufzeitkomplexität (Time Complexity) an, wie viele Berechnungsschritte ein Algorithmus ausführen muss.
| Beispiel |
| Aufwand des Bubble-Sort-Algorithmus
Speicherplatzkomplexität: konstant O(1) Der Algorithmus Bubble-Sort sortiert eine Liste, indem er benachbarte Elemente vergleicht und gegebenenfalls vertauscht. Unabhängig davon, wie viele Elemente die Liste enthält, benötigt er eine konstante Menge an zusätzlichem Speicher für Schleifen- und Hilfsvariablen. Die Laufzeitkomplexität des Algorithmus ist in allen Fällen quadratisch, da er n-mal eine äußere und n-mal eine innere Schleife durchlaufen muss um alle Elemente der Liste miteinander zu vergleichen (n · n = n²).
|
Komplexitätsklassen (Funktionsklassen) von Algorithmen
Algorithmen werden von sehr effizient bis extrem ineffizient klassifiziert. Die aufsteigende Reihenfolge der der Klassen ist O(1) < O(log n) < O(√n) < O(n) < O(n log n) < O(n2) < O(n3) < O(nk) < O(2n) < O(n!) < O(nn). Ihre Bezeichnung erfolgt mathematisch.
sehr effizient:
Konstante Komplexität – Klasse O(1)
Konstante Algorithmen sind sehr effizient, da sich ihr Aufwand nicht ändert. Ihre Laufzeit ist unabhängig von der Eingabegröße. Ein Idealfall, der meist nur bei trivialen Problemen auftritt, wie zum Beispiel ein direkter Treffer bei der linearen Suche (Best Case).
effizient:
Logarithmische Komplexität – Klasse O(log n)
Logarithmische Algorithmen sind effizient. Ihr Aufwand wächst mit zunehmender Problemgröße nur um eine konstante Zeit länger als die Eingabegröße. Algorithmen dieser Klasse sind extrem schnell und benötigen meist wenig zusätzlichen Speicher für Variablen auf dem Stack. Ein Beispiel ist die binäre Suche in einem sortierten Array. Logarithmische Algorithmen eignen sich für große Datenmengen und werden oft bei künstlicher Intelligenz eingesetzt.
relativ effizient:
Lineare Komplexität – Klasse O(n)
Bei linearen Algorithmen wächst der Aufwand proportional zur Eingabegröße. Sie sind relativ effizient und eignen sich auch für große Eingabemengen, wenn keine komplexen Berechnungen durchgeführt werden. Die Laufzeit verdoppelt sich bei Verdoppelung der Eingabegröße, wie z.B. bei der linearen Suche in einem unsortierten Array.
Sublineare, quadratwurzel-proportionale Komplexität – Klasse O(√n)
Bei sublinearen Algorithmen wächst der Aufwand etwas langsamer als bei linearen. Sie eignen sich für mittlere Eingabemengen und benötigen meist wenig zusätzlichen Speicher für Variablen und einfache Berechnungen. Beispiele für sublineare Komplexität sind Algorithmen die prüfen, ob eine Zahl eine Primzahl oder das Quadrat einer Ganzzahl ist.
Quasilineare Komplexität – Klasse O(n log n)
Bei quasilinearen Algorithmen wächst der Aufwand mit zunehmender Eingabegröße moderat. Bei Verdopplung der Eingabegröße, wächst die Laufzeit etwas mehr als doppelt. Sie sind ideal für große Eingabemengen, weil log n klein bleibt. Beispiele für Algorithmen mit quasilinearer Laufzeitkomplexität sind die Sortieralgorithmen Merge-Sort sowie Quick-Sort im Average Case.
ineffizient:
Quadratische Komplexität – Klasse O(n2)
Quadratische Algorithmen sind ineffizient und eignen sich für mittlere Problemgrößen. Die Laufzeit wächst mit der Eingabegröße quadratisch und vervierfacht sich bei Verdopplung. Der Speicherplatz bleibt oft konstant, wächst aber quadratisch bei Verwendung von 2D-Datenstrukturen mit verschachtelten Schleifen. Ein Beispiel ist der Sortieralgorithmus Insertion-Sort, der eine Liste durch Einfügen sortiert.
sehr ineffizient:
Kubische Komplexität – Klasse O(n3)
Kubische Algorithmen sind sehr ineffizient und eignen sich nur für kleine Problemgrößen. Die Laufzeit wächst kubisch mit der Eingabegröße n und verachtfacht sich bei Verdopplung. Der Speicherplatz wächst bei Verwendung von 3D-Datenstrukturen kubisch. Ein Beispiel ist die klassische Matrix-Multiplikation mit drei geschachtelten Schleifen.
Polynomiale Komplexität – Klasse O(nk)
Auch polynomiale Algorithmen sind sehr ineffizient. Die Laufzeit wächst als Potenz k der Eingabegröße und der Speicherplatz kann bei großen k exponentiell wachsen. Sie eignen sich hauptsächlich für kleine Problemgrößen, gelten aber bei kleinen Potenzen als handhabbar. Zum Beispiel berechnet ein polynomialer Algorithmus alle Möglichkeiten, eine Zahl n als Summe mit k positiven Zahlen zu bilden.
extrem ineffizient:
Exponentielle Komplexität – Klasse O(2n)
Exponentielle Algorithmen sind extrem ineffizient und in der Praxis fast wertlos, selbst bei kleinen oder moderaten Problemgrößen. Die Laufzeit verdoppelt sich mit jeder zusätzlichen Eingabegröße und der Speicherplatz kann – je nach Rekursionstiefe – exponentiell wachsen. Beispielsweise hat die rekursive Berechnung der Fibonacci-Zahlen eine exponentielle Komplexität.
Faktorielle Komplexität – Klasse O(n!)
Auch Faktorielle Algorithmen sind extrem ineffizient, werden aber in der Praxis sehr selten auch für größere Eingabemengen eingesetzt. Die Laufzeit wächst noch schneller als exponentiell und auch der Speicherplatz wächst meist faktoriell mit der Eingabegröße, insbesondere wenn viele Teilprobleme oder Zustände gespeichert werden. Ein Beispiel ist das Travelling Salesman Problem (TSP).
Exponentiale (superexponentielle) Komplexität – Klasse O(nn)
Auch Exponentiale (superexponentiellen) Algorithmen sind extrem ineffizient und werden in der Praxis kaum verwendet, auch nicht bei kleinen Problemgrößen. Die Laufzeit wächst noch schneller als faktoriell. Sie sind extrem speicherintensiv, meist exponentiell. Ein Beispiel ist das Placement Problem, bei dem n verschiedene Objekte in n unterschiedliche Behälter gelegt werden.
Optimale und Brute-Force-Algorithmen
Ein optimaler Algorithmus löst ein bestimmtes Problem am effizientesten, wie beispielsweise der Dijkstra-Algorithmus, der von einem Startknoten die kürzesten Wege zu allen anderen Knoten berechnet.
Das Gegenteil sind Brute-Force-Algorithmen, die alle potenziellen Lösungen durchprobieren, bis die richtige gefunden ist. Ein Beispiel ist das Passwort-Cracking.
Die Kommentarfunktion ist deaktiviert, aber Trackbacks und Dingbacks sind offen.