Scheda di esercizi di Algoritmi e complessità con soluzioni

Che cosa descrive il tempo di esecuzione nel caso medio?

1. AIl tempo per un input di lunghezza media
2. BIl tempo atteso rispetto a una data distribuzione degli input di dimensione n
3. CIl valore intermedio tra i tempi di esecuzione nel caso migliore e nel caso peggiore
4. DIl tempo sul computer più diffuso

Qual è la complessità temporale della ricerca lineare in un array non ordinato di n elementi (caso peggiore)?

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

La complessità spaziale misura:

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

Qual è la complessità temporale del quicksort nel caso peggiore?

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

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

1. AO(n log n)
2. BO(1)
3. CO(n)
4. DO(log 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)

Usando il teorema dell'esperto (master theorem), T(n) = 8T(n/2) + O(n²) ha come soluzione:

1. AΘ(n³)
2. BΘ(n² log n)
3. CΘ(n log n)
4. DΘ(n²)

Il problema dello zaino 0/1 risolto con la programmazione dinamica richiede tempo O(nW). Perché si dice pseudo-polinomiale?

1. APerché n è sempre piccolo
2. BPerché l'algoritmo è randomizzato e il suo tempo di esecuzione varia a ogni input
3. CPerché funziona solo per W = 0
4. DW è un numero, quindi il tempo è esponenziale nel numero di bit usati per scrivere W