Scheda di esercizi di Algoritmi e complessità con soluzioni

Che cosa significa che un'operazione ha tempo O(1)?

1. APuò essere eseguita una sola volta
2. BRichiede sempre esattamente un secondo
3. CIl suo tempo di esecuzione non cresce con la dimensione dell'input
4. DElabora esattamente un elemento per ogni secondo di tempo di esecuzione

Che cosa descrive il tempo di esecuzione nel caso peggiore di un algoritmo?

1. AIl tempo atteso su un input casuale di dimensione n
2. BIl tempo massimo impiegato su tutti gli input di dimensione n
3. CIl tempo impiegato su un computer lento
4. DIl tempo impiegato sull'input più piccolo

Qual è la complessità temporale nel caso migliore dell'insertion sort, su un array già ordinato?

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

Qual è la soluzione della ricorrenza T(n) = T(n − 1) + O(1)?

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

In un array ordinato cerchi due elementi la cui somma sia un valore dato muovendo un puntatore da ciascuna estremità verso l'interno. Qual è la complessità temporale?

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

Qual è la complessità temporale ammortizzata dell'aggiunta in coda a un array dinamico che raddoppia la capacità quando è pieno?

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

L'insertion sort richiede O(n) su un input ordinato. Questo contraddice il limite inferiore Ω(n log n) per l'ordinamento per confronti?

1. ANo, perché l'insertion sort non è un ordinamento per confronti
2. BNo, il limite inferiore si applica al caso peggiore su tutti gli input, non a ogni input
3. CSì, ma solo per array più corti di 100
4. DSì, quindi il limite inferiore è sbagliato

La moltiplicazione di Karatsuba soddisfa T(n) = 3T(n/2) + O(n). Qual è la soluzione?

1. AΘ(n³)
2. BΘ(n^{log₂ 3}), circa n^1,585
3. CΘ(n²)
4. DΘ(n log n)