Scheda di esercizi di Algoritmi e complessità con soluzioni

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

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

Un algoritmo O(n²) impiega 1 secondo per n = 1000. Circa quanto impiega per n = 2000?

1. A4 secondi
2. B2 secondi
3. C8 secondi
4. D1 secondo

Che cos'è un algoritmo?

1. AUna struttura dati che memorizza numeri
2. BUna sequenza finita di passi ben definiti che risolve un problema
3. CQualsiasi programma con un'interfaccia grafica
4. DUn linguaggio di programmazione progettato per scrivere formule matematiche

Il limite inferiore per l'ordinamento basato su confronti nel caso peggiore è:

1. AΩ(n)
2. BΩ(log n)
3. CΩ(n²)
4. DΩ(n log 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 complessità temporale dell'algoritmo standard di programmazione dinamica per la sottosequenza comune più lunga di stringhe di lunghezze m e n?

1. AO(m + n)
2. BO(mn log n)
3. CO(2^m+n)
4. DO(mn)

Qual è la complessità temporale della costruzione di un heap binario da n elementi non ordinati con il metodo bottom-up?

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

Quale limite è corretto per log(n!)?

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