Scheda di esercizi di Algoritmi e complessità con soluzioni

Quale notazione descrive un limite superiore della crescita?

1. AO grande (Big O)
2. BTheta grande (Big Theta)
3. COmega grande (Big Omega)
4. DOmega piccolo (little omega)

Che cosa significa f(n) = Θ(g(n))?

1. Af cresce strettamente più lentamente di g
2. Bf cresce strettamente più velocemente di g
3. Cf è sempre minore di g per ogni n, quindi g la limita superiormente ma mai inferiormente
4. Df cresce allo stesso ritmo di g, limitata superiormente e inferiormente da multipli costanti di g

La complessità spaziale misura:

1. ALe dimensioni fisiche del computer
2. BIl numero di righe di codice
3. CLa quantità di memoria di cui un algoritmo ha bisogno al crescere dell'input
4. DLo spazio su disco del file del programma una volta compilato

Una funzione esegue un ciclo di n iterazioni e poi, separatamente, un altro ciclo di n iterazioni. Qual è la sua complessità temporale?

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

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

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

Ordini una volta un array di n elementi e poi rispondi a k query di appartenenza con la ricerca binaria. Qual è il costo totale?

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

Quale affermazione su P e NP è corretta?

1. ANP significa «non polinomiale»
2. BÈ stato dimostrato che P ≠ NP
3. COgni problema in P appartiene anche a NP
4. DLe soluzioni dei problemi NP non possono essere verificate rapidamente

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

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