Scheda di esercizi di Algoritmi e complessità con soluzioni

Che cosa significa che un'operazione ha tempo O(1)?

1. AElabora esattamente un elemento per ogni secondo di tempo di esecuzione
2. BIl suo tempo di esecuzione non cresce con la dimensione dell'input
3. CRichiede sempre esattamente un secondo
4. DPuò essere eseguita una sola volta

Quanto vale log₂ 1024?

1. A10
2. B32
3. C12
4. D512

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 quicksort usa sempre il primo elemento come pivot. Su quale input mostra il comportamento del caso peggiore?

1. AUn array in ordine casuale
2. BUn array di lunghezza 2
3. CUn array già ordinato
4. DUn array con elementi tutti diversi

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)

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

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

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

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

Quale definizione della classe P è corretta?

1. AProblemi che si possono risolvere in parallelo
2. BProblemi le cui soluzioni si possono verificare ma mai trovare in tempo polinomiale
3. CProblemi decisionali risolvibili da un algoritmo deterministico in tempo polinomiale
4. DProblemi che richiedono tempo esponenziale su ogni computer