Komplexität der Algorithmen

03. 08. 2021

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	n²	n²	1	Ja
Einfügungssortierung	n	n²	n²	1
Auswahlsortierung	n²	n²	n²	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)	n²	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))²	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: