Hi there! Deze webpagina behandelt de ruimte en tijd Big-O complexiteiten van veelgebruikte algoritmen in de informatica. Toen ik me in het verleden voorbereidde op technische interviews, spendeerde ik uren op het internet om de beste, gemiddelde en slechtste complexiteit van zoek- en sorteeralgoritmen bij elkaar te zoeken, zodat ik niet voor verrassingen kwam te staan als er naar gevraagd werd. De laatste jaren heb ik interviews afgenomen bij verschillende start-ups in Silicon Valley, en ook bij grotere bedrijven, zoals Google, Facebook, Yahoo, LinkedIn en Uber, en elke keer als ik me op een interview voorbereidde, dacht ik bij mezelf “Waarom heeft niemand een mooi Big-O spiekbriefje gemaakt?”. Dus, om jullie allemaal een hoop tijd te besparen, heb ik er één gemaakt. Veel plezier ermee! – Eric
Kijk eens naar El Grapho, een bibliotheek voor het visualiseren van grafieken met ondersteuning voor miljoenen knooppunten en randen
Big-O-complexiteitsgrafiek
Horrible |
Bad |
Fair |
Good |
Excellent |
Common Data Structure Operations
| Data Structure | Tijd Complexity | Space Complexity | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Gemiddelde | Worst | Worst | Toegang | Zoeken | Invoegen | Verwijderen | Toegang | Zoeken | Invoegen | Wissen |
| 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) |
|
Θ(n) |
Θ(n) |
Θ(1) |
Θ(1) |
O(n) |
O(n)O(1) |
O(1) |
O(n) |
||
Θ(n) |
Θ(n) |
Θ(1) |
Θ(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
|
| Skip Lijst | Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
O(n) |
O(n)O(n) |
O(n) |
O(n log(n)) |
|
| Hash-tabel | N/A |
Θ(1) |
Θ(1) |
Θ(1) |
N/A |
O(n) |
O(n) |
O(n) |
O(n) |
Θ(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-Boom | Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
O(log(n)) |
O(log(n))O(log(n)) |
O(log(n)) |
O(n) |
|
Θ(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) |
|
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
|
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
O(n) |
O(n) |
O(n) |
O(n) |
O(n) |
|
Array sorteeralgoritmen
| Algoritme | Tijdcomplexiteit | Ruimtecomplexiteit | ||
|---|---|---|---|---|
| Beste | Gemiddelde | Slechtste | Slechtste | |
| 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) |
| Bubbelsortering | Ω(n) |
Θ(n^2)O(n^2) |
O(1) |
|
| Insertion Sort | Ω(n) |
Θ(n^2) |
O(n^2) |
O(1) |
Ω(n^2) |
Θ(n^2) |
O(n^2) |
O(1) |
|
| Boom Sorteren | Ω(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) |
| Bucket Sort | Ω(n+k) |
Θ(n+k) |
O(n^2) |
O(n) |
| Radix Sort | Ω(nk) |
Θ(nk) |
O(nk) |
O(n+k) |
| Telsortering | Ω(n+k) |
Θ(n+k) |
O(n+k) |
O(k) |
| Cubesort | Ω(n) |
Θ(n log(n)) |
O(n log(n)) |
O(n) |
Leer meer
- Het coderingsinterview kraken: 150 Programmeervragen en oplossingen
- Introduction to Algorithms, 3rd Edition
- Data Structures and Algorithms in Java (2nd Edition)
- High Performance JavaScript (Build Faster Web Application Interfaces)
Geef de officiële Big-O Cheat Sheet Poster
Contributors
- 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
Betere deze pagina
Bewerk deze tabellen!