Scheda di esercizi di Algoritmi e complessità con soluzioni

Che cosa descrive il tempo di esecuzione nel caso peggiore di un algoritmo?

1. AIl tempo atteso su un input casuale di dimensione n
2. BIl tempo impiegato sull'input più piccolo
3. CIl tempo massimo impiegato su tutti gli input di dimensione n
4. DIl tempo impiegato su un computer lento

Qual è la complessità temporale per trovare il valore massimo in un array non ordinato di n numeri?

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

Quanto vale log₂ 1024?

1. A32
2. B512
3. C10
4. D12

Qual è il tempo di esecuzione del radix sort LSD su n interi con d cifre in base k?

1. AO(n log n)
2. BO(d(n + k))
3. CO(dn log k)
4. DO(n²)

Quale algoritmo di ordinamento è stabile?

1. AQuicksort (tipica versione in loco)
2. BSelection sort (versione tipica)
3. CMerge sort
4. DHeap sort

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

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

Come si classifica il problema del commesso viaggiatore?

1. AÈ in P perché l'algoritmo di Dijkstra lo risolve visitando ogni città una sola volta
2. BÈ indecidibile
3. CLa versione decisionale è in P ma quella di ottimizzazione è NP-completa
4. DLa versione decisionale è NP-completa e la versione di ottimizzazione è NP-difficile

Qual è la complessità temporale di: for i = 1 to n: for (j = i; j ≤ n; j = j + i) lavoro O(1)?

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