Scheda di esercizi di Algoritmi e complessità con soluzioni

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

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

Quale strategia di progettazione usa il merge sort?

1. AForza bruta
2. BDivide et impera
3. CProgrammazione dinamica
4. DScelta greedy (golosa)

Qual è la complessità temporale della ricerca binaria in un array ordinato?

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

Quanti livelli ha la ricorsione del merge sort per un array di n elementi?

1. ACirca n
2. BCirca log₂ n
3. CCirca n / 2
4. DCirca √n

Che cosa calcola l'algoritmo di Floyd–Warshall, e con quale velocità?

1. AUn albero ricoprente minimo in O(E log V)
2. BI cammini minimi da un vertice sorgente a tutti gli altri in O(V + E)
3. CI cammini minimi tra tutte le coppie di vertici in O(V³)
4. DUn ordinamento topologico in O(V²)

Quanto spazio di stack usa una semplice funzione fattoriale ricorsiva fact(n) = n × fact(n − 1)?

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

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

1. AΘ(n² log n)
2. BΘ(n³)
3. CΘ(n²)
4. DΘ(n 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 log n)
3. CO(n²)
4. DO(n)