Scheda di esercizi di Algoritmi e complessità con soluzioni

Quanta memoria aggiuntiva usa un merge sort standard su array?

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

Qual è la complessità temporale nel caso migliore dell'insertion sort, su un array già ordinato?

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

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

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

La ricorrenza T(n) = 2T(n/2) + O(n) ha come soluzione:

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

La programmazione dinamica è utile quando un problema presenta:

1. ANessun sottoproblema, quindi si risolve in un solo passo
2. BSolo input casuali
3. CUn unico ciclo
4. DSottoproblemi sovrapposti e sottostruttura ottima

Che cosa misura l'analisi ammortizzata?

1. AIl costo atteso su input casuali
2. BIl costo medio per operazione su una sequenza di operazioni nel caso peggiore
3. CIl costo della singola operazione più costosa in un punto qualsiasi della sequenza
4. DIl costo di un algoritmo sull'input migliore

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)

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

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