Scheda di esercizi di Algoritmi e complessità con soluzioni

Quale di questi tempi di esecuzione è polinomiale?

1. AO(2ⁿ)
2. BO(n!)
3. CO(n³)
4. DO(nⁿ)

Quale di queste cresce più lentamente quando n diventa grande?

1. AO(log n)
2. BO(n)
3. CO(n²)
4. DO(n log n)

La complessità spaziale misura:

1. ALa quantità di memoria di cui un algoritmo ha bisogno al crescere dell'input
2. BIl numero di righe di codice
3. CLe dimensioni fisiche del computer
4. DLo spazio su disco del file del programma una volta compilato

Perché molte routine di ordinamento delle librerie passano all'insertion sort per sottoarray molto piccoli?

1. AL'insertion sort è O(n log n) nel caso peggiore
2. BGli algoritmi ricorsivi non gestiscono array con meno di 10 elementi
3. CL'insertion sort ha poco overhead ed è veloce su input piccoli o quasi ordinati
4. DL'insertion sort usa meno memoria di qualsiasi altro algoritmo di ordinamento per input grandi

La complessità temporale del Fibonacci ricorsivo ingenuo (fib(n) = fib(n−1) + fib(n−2)) è:

1. ALineare
2. BCostante
3. CEsponenziale
4. DLogaritmica

Quale affermazione su una funzione ricorsiva senza un caso base raggiungibile è corretta?

1. AContinua a chiamare se stessa finché lo stack delle chiamate va in overflow
2. BIl compilatore la trasforma sempre in un ciclo che termina in modo sicuro
3. CViene eseguita in tempo O(1)
4. DRestituisce automaticamente 0

Perché una ricerca in una tabella hash è in media O(1) ma nel caso peggiore O(n)?

1. ALe chiavi devono prima essere ordinate
2. BGli array hanno accesso O(n)
3. CMolte chiavi possono collidere nello stesso bucket
4. DLe funzioni hash sono lente

Perché qualsiasi ricerca basata su confronti in un array ordinato richiede Ω(log n) confronti nel caso peggiore?

1. AUn albero di decisione con n esiti possibili deve avere profondità almeno log₂ n
2. BOgni elemento deve essere confrontato almeno una volta
3. COgni confronto richiede un tempo logaritmico
4. DLa ricerca binaria è l'unico algoritmo possibile e richiede log₂ n confronti