Scheda di esercizi di Algoritmi e complessità con soluzioni

Quali sono i tre passi di un algoritmo divide et impera?

1. ALeggi, calcola, scrivi
2. BDividi, risolvi (impera), combina
3. COrdina, cerca, restituisci
4. DIndovina, verifica, ripeti

Un problema si dice di solito trattabile se:

1. ANon ha soluzione
2. BPuò essere risolto in tempo polinomiale
3. CPuò essere risolto solo provando ogni possibilità
4. DPuò essere risolto in tempo costante

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

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

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

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

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. BL'insertion sort ha poco overhead ed è veloce su input piccoli o quasi ordinati
3. CL'insertion sort usa meno memoria di qualsiasi altro algoritmo di ordinamento per input grandi
4. DGli algoritmi ricorsivi non gestiscono array con meno di 10 elementi

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(V + E)
4. DO(E log V)

Qual è il costo ammortizzato dell'incremento di un contatore binario, dato che un incremento può invertire molti bit?

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

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

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