Scheda di esercizi di Algoritmi e complessità con soluzioni

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

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

Un ciclo parte con i = 1 e raddoppia i a ogni iterazione finché i > n. Quante iterazioni esegue?

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

Quale classe di complessità cresce più rapidamente per n grande?

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

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

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

Qual è la complessità temporale della moltiplicazione di due matrici n × n con il triplo ciclo standard?

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

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

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

Quale affermazione sulla notazione o piccolo è corretta?

1. A2n = o(n), perché 2n cresce lentamente
2. Bn² = o(n)
3. Cn = o(n), perché ogni funzione è o piccolo di se stessa
4. Dn = o(n²), ma n non è o(n)

Qual è la differenza tra un problema indecidibile e uno intrattabile?

1. AI problemi indecidibili sono in NP, mentre quelli intrattabili sono in P
2. BEntrambi significano che il problema non ha alcun algoritmo
3. CPer un problema indecidibile non esiste alcun algoritmo valido per tutti gli input; uno intrattabile ne ha uno, ma è troppo lento
4. DI problemi intrattabili non si possono risolvere con alcun algoritmo, mentre quelli indecidibili richiedono solo tempo esponenziale