Hallo! Diese Webseite deckt die räumlichen und zeitlichen Big-O-Komplexitäten von häufigen Algorithmen ab, die in der Informatik verwendet werden. Als ich mich in der Vergangenheit auf technische Interviews vorbereitet habe, habe ich Stunden damit verbracht, das Internet zu durchforsten, um die besten, durchschnittlichen und schlimmsten Komplexitäten für Such- und Sortieralgorithmen zusammenzustellen, damit ich nicht ratlos bin, wenn ich danach gefragt werde. In den letzten Jahren habe ich bei mehreren Silicon Valley-Startups und auch bei einigen größeren Unternehmen wie Google, Facebook, Yahoo, LinkedIn und Uber Vorstellungsgespräche geführt, und jedes Mal, wenn ich mich auf ein Vorstellungsgespräch vorbereitet habe, dachte ich mir: „Warum hat nicht jemand einen schönen Big-O-Spickzettel erstellt?“. Um Ihnen allen eine Menge Zeit zu ersparen, habe ich einen solchen erstellt. Viel Spaß damit! – Eric
Schauen Sie sich El Grapho an, eine Graphdaten-Visualisierungsbibliothek, die Millionen von Knoten und Kanten unterstützt
Big-O Complexity Chart
Horrible |
Bad |
Fair |
Good |
Excellent |
Gängige Datenstruktur-Operationen
| Datenstruktur | Zeitkomplexität | Raumkomplexität | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Durchschnitt | Schlechteste | Schlechteste | |||||||
| Zugriff | Suchen | Einfügen | Löschen | Zugriff | Suchen | Einfügen | Löschen | ||
| Array | Θ(1) |
Θ(n) |
Θ(n) |
Θ(n) |
O(1) |
O(n) |
O(n) |
O(n) |
O(n) |
| Stack | Θ(n) |
Θ(n) |
Θ(1) |
Θ(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
| Queue | Θ(n) |
Θ(n) |
Θ(1) |
Θ(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
Singly-Verknüpfte Liste | Θ(n) |
Θ(n) |
Θ(1) |
Θ(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
Doppel-Verknüpfte Liste | Θ(n) |
Θ(n) |
Θ(1) |
Θ(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
| Sprungliste | Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
O(n) |
O(n) |
O(n) |
O(n) |
O(n log(n)) |
| Hashtabelle | N/A |
Θ(1) |
Θ(1) |
Θ(1) |
N/A |
O(n) |
O(n) |
O(n) |
O(n) |
| Binärer Suchbaum | Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
O(n) |
O(n) |
O(n) |
O(n) |
O(n) |
N/A |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
N/A |
O(n) |
O(n) |
O(n) |
O(n) |
|
| B-Baum | Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
Rot-Schwarzer Baum | Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
N/A |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
N/A |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
|
| AVL-Baum | Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
KD Tree | Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
O(n) |
O(n) |
O(n) |
O(n) |
O(n) |
Array-Sortieralgorithmen
| Algorithmus | Zeitkomplexität | Raumkomplexität | ||
|---|---|---|---|---|
| Best | Durchschnitt | Schlechteste | Schlechteste | |
| Quicksort | Ω(n log(n)) |
Θ(n log(n)) |
O(n^2) |
O(log(n)) |
| Mergesort | Ω(n log(n)) |
Θ(n log(n)) |
O(n log(n)) |
O(n) |
| Timsort | Ω(n) |
Θ(n log(n)) |
O(n log(n)) |
O(n) |
| Heapsort | Ω(n log(n)) |
Θ(n log(n)) |
O(n log(n)) |
O(1) |
| Bubble Sort | Ω(n) |
Θ(n^2) |
O(n^2) |
O(1) |
| Einfügungssortierung | Ω(n) |
Θ(n^2) |
O(n^2) |
O(1) |
| Sortierung der Auswahl | Ω(n^2) |
Θ(n^2) |
O(n^2) |
O(1) |
| Baumsortierung | Ω(n log(n)) |
Θ(n log(n)) |
O(n^2) |
O(n) |
Shell Sort | Ω(n log(n)) |
Θ(n(log(n))^2) |
O(n(log(n))^2) |
O(1) |
| Eimersortierung | Ω(n+k) |
Θ(n+k) |
O(n^2) |
O(n) |
| Radix Sort | Ω(nk) |
Θ(nk) |
O(nk) |
O(n+k) |
| Zählende Sortierung | Ω(n+k) |
Θ(n+k) |
O(n+k) |
O(k) |
| Cubesort | Ω(n) |
Θ(n log(n)) |
O(n log(n)) |
O(n) |
Weiter lernen
- Cracking the Coding Interview: 150 Programmierfragen und Lösungen
- Einführung in Algorithmen, 3rd Edition
- Datenstrukturen und Algorithmen in Java (2nd Edition)
- High Performance JavaScript (Build Faster Web Application Interfaces)
Get the Official Big-O Spickzettel Poster
Beitragende
- Eric Rowell
- Quentin Pleple
- Michael Abed
- Nick Dizazzo
- Adam Forsyth
- Felix Zhu
- Jay Engineer
- Josh Davis
- Nodir Turakulov
- Jennifer Hamon
- David Dorfman
- Bart Massey
- Ray Pereda
- Si Pham
- Mike Davis
- mcverry
- Max Hoffmann
- Bahador Saket
- Damon Davison
- Alvin Wan
- Alan Briolat
- Drew Hannay
- Andrew Rasmussen
- Dennis Tsang
- Vinnie Magro
- Adam Arold
- Alejandro Ramirez
- Aneel Nazareth
- Rahul Chowdhury
- Jonathan McElroy
- steven41292
- Brandon Amos
- Joel Friedly
- Casper Van Gheluwe
- Eric Lefevre-.Ardant
- Oleg
- Renfred Harper
- Piper Chester
- Miguel Amigot
- Apurva K
- Matthew Daronco
- Yun-Cheng Lin
- Clay Tyler
- Orhan Can Ozalp
- Ayman Singh
- David Morton
- Aurelien Ooms
- Sebastian Paaske Torholm
- Koushik Krishnan
- Drew Bailey
- Robert Burke
Make this Page Better
Bearbeiten Sie diese Tabellen!