Scheda di esercizi di Algoritmi e complessità con soluzioni

Qual è il tempo di esecuzione del counting sort per n interi nell'intervallo da 0 a k?

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

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

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

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

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

Quanto spazio di stack usa una semplice funzione fattoriale ricorsiva fact(n) = n × fact(n − 1)?

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

In un array ordinato cerchi due elementi la cui somma sia un valore dato muovendo un puntatore da ciascuna estremità verso l'interno. Qual è la complessità temporale?

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

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

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

Quali due cose bisogna dimostrare per provare che un problema decisionale X è NP-completo?

1. AX non ha un algoritmo polinomiale, e X è decidibile
2. BX si riduce a un problema in P, e X è in NP
3. CX è in P, e X si riduce a SAT
4. DX è in NP, e un problema NP-completo noto si riduce a X in tempo polinomiale

Un problema è NP-completo se:

1. AÈ risolvibile in tempo polinomiale
2. BÈ impossibile da risolvere
3. CÈ al di fuori di NP ma più difficile di tutti i problemi NP, come il problema della fermata
4. DAppartiene a NP e ogni problema NP si riduce a esso in tempo polinomiale