Notazione Big O, principali algoritmi di ordinamento e ricerca e schemi di ricorsione richiesti nei colloqui tecnici e nei corsi universitari.
38 cards · basic cards · AI-written, checked twice. Edit anything.
- Che cosa misura la notazione Big O?
Show answer
Come crescono il tempo di esecuzione o lo spazio richiesti da un algoritmo all'aumentare della dimensione dell'input.- Definisci la complessità temporale O(1).
Show answer
Tempo costante: il tempo di esecuzione non cambia al variare della dimensione dell'input.- Definisci la complessità temporale O(n).
Show answer
Tempo lineare: il tempo di esecuzione cresce in modo proporzionale alla dimensione dell'input n.- Definisci la complessità temporale O(log n).
Show answer
Tempo logaritmico: il tempo di esecuzione cresce con il logaritmo della dimensione dell'input.- Definisci la complessità temporale O(n^2).
Show answer
Tempo quadratico: il tempo di esecuzione cresce con il quadrato della dimensione dell'input.- Definisci la complessità temporale O(n log n).
Show answer
Tempo linearitmico: il tempo di esecuzione è n volte il logaritmo di n.- Definisci la complessità temporale O(2^n).
Show answer
Tempo esponenziale: il tempo di esecuzione raddoppia a ogni aumento della dimensione dell'input.- Qual è la complessità temporale dell'accesso a un elemento di un array tramite indice?
Show answer
O(1), tempo costante.- Qual è la complessità temporale della ricerca di un valore in un array non ordinato?
Show answer
O(n), tempo lineare.- Qual è la complessità temporale della ricerca binaria su un array ordinato?
Show answer
O(log n), tempo logaritmico.- Quale condizione deve essere vera per un array prima di poter usare la ricerca binaria?
Show answer
L'array deve essere ordinato.- Qual è la complessità temporale dell'inserimento di un elemento all'inizio di un array?
Show answer
O(n), tempo lineare.- Qual è la complessità temporale dell'aggiunta di un elemento in coda a un array dinamico con capacità disponibile?
Show answer
O(1) ammortizzato, tempo costante.- Qual è la complessità temporale media della ricerca in una tabella hash?
Show answer
O(1), tempo costante, con una buona funzione hash.- Qual è la complessità temporale del quicksort nel caso medio?
Show answer
O(n log n), tempo linearitmico.
FlashKeepers