Salve! Questa pagina web copre le complessità Big-O spaziali e temporali di algoritmi comuni usati in Informatica. Quando mi preparavo per i colloqui tecnici in passato, mi ritrovavo a passare ore a strisciare su internet per mettere insieme le complessità del caso migliore, medio e peggiore per gli algoritmi di ricerca e di ordinamento in modo da non essere bloccato quando mi venivano chieste informazioni. Nel corso degli ultimi anni, ho fatto colloqui in diverse startup della Silicon Valley, e anche in alcune aziende più grandi, come Google, Facebook, Yahoo, LinkedIn e Uber, e ogni volta che mi sono preparato per un colloquio, ho pensato tra me e me “Perché qualcuno non ha creato un bel foglio di calcolo Big-O? Così, per risparmiare a tutti voi un sacco di tempo, sono andato avanti e ne ho creato uno. Buon divertimento! – Eric
Guardate El Grapho, una libreria di visualizzazione di dati grafici che supporta milioni di nodi e bordi
Big-O Complexity Chart
Horrible |
Bad |
Fair |
Good |
Excellent |
Operazioni comuni della struttura dei dati
| Struttura dei dati | complessità temporale | complessità spaziale | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Media | Peggiore | Peggiore | ||||||||
| Accesso | Ricerca | Inserimento | Deliminazione | Accesso | Ricerca | Inserimento | Cancellazione | |||
| 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) |
|
| Queueue | Θ(n) |
Θ(n) |
Θ(1) |
Θ(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
|
| Singly-Linked List | Θ(n) |
Θ(n) |
Θ(1) |
Θ(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
|
| Doubly-Linked List | Θ(n) |
Θ(n) |
Θ(1) |
Θ(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
|
| Skip List | Θ(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) |
|
| Albero di ricerca binaria | Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
O(n) |
O(n) |
O(n) |
O(n) |
O(n) |
|
| Albero cartesiano | N/A |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
N/A |
O(n) |
O(n) |
O(n) |
O(n) |
|
| B-Albero | Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
|
| Rosso-Albero nero | Θ(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) |
|
| Albero AVL | Θ(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) |
|
Algoritmi di ordinamento delle matrici
| Algoritmo | Complessità temporale | Complessità spaziale | |||
|---|---|---|---|---|---|
| Migliore | Media | Peggiore | Peggiore | ||
| 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) |
|
| Insertion Sort | Ω(n) |
Θ(n^2) |
O(n^2) |
O(1) |
|
| Selezione Ordina | Ω(n^2) |
Θ(n^2) |
O(n^2) |
O(1) |
|
| Ordinamento ad albero | Ω(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) |
|
| Counting Sort | Ω(n+k) |
Θ(n+k) |
O(n+k) |
O(k) |
|
| Cubesort | Ω(n) |
Θ(n log(n)) |
O(n log(n)) |
O(n) |
|
Impara di più
- Cracking the Coding Interview: 150 domande di programmazione e soluzioni
- Introduzione agli algoritmi, 3rd Edition
- Data Structures and Algorithms in Java (2nd Edition)
- High Performance JavaScript (Build Faster Web Application Interfaces)
Get the Official Big-O Poster ufficiale
Contribuenti
- 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
Migliora questa pagina
Modifica queste tabelle!