Komplexität der Algorithmen
Jeder Algorithmus hat seine eigene Komplexität, die in mathematischer Notation ausgedrückt werden kann. Diese Übersicht zeigt die typische Komplexität von Algorithmen in Abhängigkeit von der Größe der Eingabedaten (d. h. der Anzahl der Elemente, mit denen sie arbeiten) und welche Arten von Algorithmen für welche Art von Aufgabe geeignet sind.
Im Allgemeinen gibt es für jede Art von Problem einen besten spezialisierten Algorithmus. Kein Algorithmus ist universell am besten, und man muss immer den Kontext kennen.
Big-O-Notation
Die Big O Notation wird verwendet, um Algorithmen danach zu klassifizieren, wie ihr Laufzeit- oder Speicherbedarf mit zunehmender Eingabegröße steigt.
Das folgende Diagramm zeigt die häufigsten Wachstumsordnungen von Algorithmen, die in Big-O-Notation angegeben sind.
Nachfolgend finden Sie eine Liste der am häufigsten verwendeten Big-O-Notationen und einen Vergleich ihrer Leistung in Bezug auf verschiedene Eingabedatengrößen.
| Big O Notation | Komplexität für 10 Elemente | Komplexität für 100 Elemente | Komplexität für 1000 Elemente |
|---|---|---|---|
| O(1) | 1 | 1 | 1 |
| O(log N) | 3 | 6 | 9 |
| O(N) | 10 | 100 | 1000 |
| O(N log N) | 30 | 600 | 9000 |
| O(N^2) | 100 | 10000 | 1000000 |
| O(2^N) | 1024 | 1.26e+29 | 1.07e+301 |
| O(N!) | 3628800 | 9.3e+157 | 4.02e+2567 |
Komplexität von Datenstrukturoperationen
| Datenstruktur | Zugriff | Suchen | Einfügen | Entfernen | Kommentar |
|---|---|---|---|---|---|
| Array | 1 | n | n | n | n |
| Stapel | n | n | n | 1 | 1 |
| Warteschlange | n | n | n | 1 | |
| Verknüpfte Liste | n | n | n | 1 | n |
| Hashtabelle | - | n | n | n | n |
| Binärer Suchbaum | n | n | n | n | Im Falle eines ausgeglichenen Baums ist die Komplexität O(log(n)). |
| B-Baum | log(n) | log(n) | log(n) | log(n) | log(n) |
| Red-Black Tree | log(n) | log(n) | log(n) | log(n) | |
| AVL-Baum | log(n) | log(n) | log(n) | log(n) | log(n) |
| Bloom-Filter | - | 1 | 1 | - | Bei der Suche nach "falsch positiven Ergebnissen" |
Komplexität von Sortieralgorithmen
| Name des Algorithmus | Bester | Durchschnitt | Schlechtester | Speicher | Stabil? | Kommentar |
|---|---|---|---|---|---|---|
| Bubble sort | n | n2 | n2 | 1 | Ja | |
| Einfügungssortierung | n | n2 | n2 | 1 | ||
| Auswahlsortierung | n2 | n2 | n2 | 1 | ||
| Heap sort | n log(n) | n log(n) | n log(n) | 1 | Nein | |
| Merge sort | n log(n) | n log(n) | n log(n) | n | Ja | |
| Quicksort | n log(n) | n log(n) | n2 | log(n) | Nein | Quicksort wird in der Regel mit O(log(n)) Stack-Komplexität durchgeführt. |
| Shell sort | n log(n) | hängt von der Reihenfolge ab | n (log(n))2 | 1 | Nein | |
| Zählende Sortierung | n + r | n + r | n + r | n + r | n + r | Ja |
| Radix-Sortierung | n * k | n * k | n * k | n + k | Ja | k - Länge des längsten Schlüssels |
Jan Barášek Mehr über den Autor
Der Autor arbeitet als leitender Entwickler und Softwarearchitekt in Prag. Er entwickelt und verwaltet große Webanwendungen, die Sie kennen und nutzen. Seit 2009 hat er einen reichen Erfahrungsschatz gesammelt, den er auf dieser Website weitergibt.
Ich werde Ihnen gerne helfen:
Kontakt