Scheda di esercizi di Algoritmi e complessità con soluzioni

Che cosa richiede la ricerca binaria al suo input?

1. ALa lunghezza dell'array deve essere una potenza di due
2. BL'array deve essere ordinato
3. CL'array non deve avere più di 1000 elementi
4. DL'array deve contenere solo numeri positivi

Il tempo di esecuzione di un algoritmo è O(n). Come si chiama questa crescita?

1. AQuadratica
2. BCostante
3. CLineare
4. DLogaritmica

Un algoritmo con due cicli annidati, ciascuno eseguito n volte, ha tipicamente quale complessità?

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

Qual è la complessità temporale dell'algoritmo di Bellman–Ford su un grafo con V vertici ed E archi?

1. AO(V + E)
2. BO(V³ × E)
3. CO(E log V)
4. DO(V × E)

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

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

Che cosa significa che un problema ha una sottostruttura ottima?

1. AIl problema ha esattamente una soluzione ottima, condivisa da ogni sottoproblema
2. BUna soluzione ottima può essere costruita da soluzioni ottime dei suoi sottoproblemi
3. CIl problema si può risolvere in tempo costante
4. DOgni sottoproblema ha la stessa dimensione

Quale limite è corretto per log(n!)?

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

Qual è la complessità temporale di: for i = 1 to n: for (j = i; j ≤ n; j = j + i) lavoro O(1)?

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