Scheda di esercizi di Algoritmi e complessità con soluzioni

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

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

Che cosa significa f(n) = Θ(g(n))?

1. Af cresce strettamente più lentamente di g
2. Bf cresce allo stesso ritmo di g, limitata superiormente e inferiormente da multipli costanti di g
3. Cf è sempre minore di g per ogni n, quindi g la limita superiormente ma mai inferiormente
4. Df cresce strettamente più velocemente di g

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

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

Circa quanti confronti richiede nel caso peggiore la ricerca binaria su un array ordinato di 1,000,000 di elementi?

1. ACirca 100
2. BCirca 20
3. CCirca 1,000
4. DCirca 500,000

È corretto dire che un algoritmo O(n²) è anche O(n³)?

1. ANo, perché per n grande n³ è minore di n²
2. BNo, perché l'O grande deve indicare sempre l'esatto tasso di crescita della funzione
3. CSì, perché l'O grande è un limite superiore e n² non cresce più velocemente di n³
4. DSì, ma solo se n è minore di 100

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

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

Perché l'algoritmo di Dijkstra può dare risultati errati quando alcuni pesi degli archi sono negativi?

1. AI numeri negativi non si possono memorizzare in una coda di priorità
2. BEntra in un ciclo infinito a ogni arco negativo
3. CFunziona solo sui grafi non orientati
4. DUn vertice viene considerato definitivo quando è estratto, ma un arco negativo successivo potrebbe ancora dargli un cammino più breve

L'algoritmo di Strassen moltiplica matrici usando 7 invece di 8 moltiplicazioni ricorsive di blocchi di metà dimensione. Qual è il suo tempo di esecuzione?

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