Cześć tam! Ta strona obejmuje złożoność czasową i przestrzenną Big-O powszechnie stosowanych algorytmów w informatyce. Przygotowując się do rozmów kwalifikacyjnych w przeszłości, spędziłem godziny na przeszukiwaniu internetu, aby zebrać najlepsze, średnie i najgorsze przypadki złożoności algorytmów wyszukiwania i sortowania, abym nie był w tyle, kiedy zostanę o nie zapytany. W ciągu ostatnich kilku lat, mam wywiady w kilku startupów Doliny Krzemowej, a także kilka większych firm, takich jak Google, Facebook, Yahoo, LinkedIn, i Uber, i za każdym razem, że przygotowany do wywiadu, myślałem sobie „Dlaczego nie ktoś stworzył ładny Big-O arkusz? Tak więc, aby zapisać wszystkie z was grzywny ludzi tonę czasu, poszedłem do przodu i stworzył jeden. Enjoy! – Eric
Sprawdź El Grapho, bibliotekę do wizualizacji danych grafowych, która obsługuje miliony węzłów i krawędzi
Big-O Complexity Chart
Horrible |
Bad |
Fair |
Good |
Excellent |
Wspólne operacje na strukturach danych
| Struktura danych | Złożoność czasowa | Złożoność przestrzenna | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Average | Worst | Worst | |||||||||||
| Access | Search | Insertion | Deletion | Access | Search | Insertion | Deletion | ||||||
| Array | Θ(1) |
Θ(n) |
Θ(n) |
Θ(n) |
Θ(n) |
O(1) |
O(n) |
O(n) |
O(n) |
O(n) |
O(n) |
O(n) |
O(n) |
| Stack | Θ(n) |
Θ(n) |
Θ(1) |
Θ(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
O(n) |
O(n) |
||
| Queue | Θ(n) |
Θ(n) |
Θ(1) |
Θ(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
||||
| Singly-.Linked List | Θ(n) |
Θ(n) |
Θ(1) |
Θ(1) |
Θ(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
|||
| Double-Linked List | Θ(n) |
Θ(n) |
Θ(1) |
Θ(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
||||
| Lista pominiętych | Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
O(n) |
O(n) |
O(n) |
O(n) |
O(n log(n)) |
|||
| Hash Table | N/A |
Θ(1) |
Θ(1) |
Θ(1) |
N/A |
O(n) |
O(n) |
O(n) |
O(n) |
||||
| Drzewo wyszukiwania binarnego | Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
O(n) |
O(n) |
O(n) |
O(n) |
O(n) |
||||
| Drzewo kartezjańskie | N/A |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
N/A |
O(n) |
O(n) |
O(n) |
O(n) |
||||
| B-Drzewo | Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
||
| Red-Black Tree | Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
||||
| Splay Tree | N/A |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
N/A |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
||||
| AVL Tree | Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
||||
| Drzewo KD | Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
O(n) |
O(n) |
O(n) |
O(n) |
O(n) |
||||
Algorytmy sortowania tablicowego
| Algorytm | Złożoność czasowa | Złożoność przestrzenna | ||
|---|---|---|---|---|
| Najlepszy | Średni | Najgorszy | Najgorszy | |
| 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) |
| Sort bąbelkowy | Ω(n) |
Θ(n^2) |
O(n^2) |
O(1) |
| Insertion Sort | Ω(n) |
Θ(n^2) |
O(n^2) |
O(1) |
| Selection Sort | Ω(n^2) |
Θ(n^2) |
O(n^2) |
O(1) |
| Sortowanie drzew | Ω(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) |
| Sortowanie kubełkowe | Ω(n+k) |
Θ(n+k) |
O(n^2) |
O(n) |
| Radix Sort | Ω(nk) |
Θ(nk) |
O(nk) |
O(n+k) |
| Sortowanie zliczające | Ω(n+k) |
Θ(n+k) |
O(n+k) |
O(k) |
| Kubesort | Ω(n) |
Θ(n log(n)) |
O(n log(n)) |
O(n) |
Learn More
- Cracking the Coding Interview: 150 Programming Questions and Solutions
- Introduction to Algorithms, 3rd Edition
- Data Structures and Algorithms in Java (2nd Edition)
- High Performance JavaScript (Build Faster Web Application Interfaces)
Get the Official Big-O Cheat Sheet Poster
Wydawcy
- 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
Ulepsz tę stronę
Edytuj te tabele!