Komplexität der Algorithmen
Obsah článku
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 Více o autorovi
Autor článku pracuje jako seniorní vývojář a software architekt v Praze. Navrhuje a spravuje velké webové aplikace, které znáte a používáte. Od roku 2009 nabral bohaté zkušenosti, které tímto webem předává dál.
Rád vám pomůžu:
Související články
Články píše Jan Barášek © 2009-2022 | Kontakt | Mapa webu
Vue.js manual | Status | Aktualizováno: ... | de
