Scheda di esercizi di Algoritmi e complessità con soluzioni

Qual è l'O grande di 3n² + 5n + 2?

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

Il tempo di esecuzione di un algoritmo è O(n). Come si chiama questa crescita?

1. ALogaritmica
2. BCostante
3. CQuadratica
4. DLineare

Qual è il caso base di una funzione ricorsiva?

1. ALa prima riga della funzione
2. BIl caso con l'input più grande, che viene gestito prima di qualsiasi chiamata ricorsiva
3. CLa chiamata che usa più memoria
4. DUn caso a cui si risponde direttamente senza un'altra chiamata ricorsiva

Quanti livelli ha la ricorsione del merge sort per un array di n elementi?

1. ACirca √n
2. BCirca log₂ n
3. CCirca n / 2
4. DCirca n

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

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

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³)

L'insertion sort richiede O(n) su un input ordinato. Questo contraddice il limite inferiore Ω(n log n) per l'ordinamento per confronti?

1. ANo, perché l'insertion sort non è un ordinamento per confronti
2. BSì, ma solo per array più corti di 100
3. CNo, il limite inferiore si applica al caso peggiore su tutti gli input, non a ogni input
4. DSì, quindi il limite inferiore è sbagliato

Perché una ricerca in una tabella hash è in media O(1) ma nel caso peggiore O(n)?

1. ALe funzioni hash sono lente
2. BGli array hanno accesso O(n)
3. CLe chiavi devono prima essere ordinate
4. DMolte chiavi possono collidere nello stesso bucket