Scheda di esercizi di Algoritmi e complessità con soluzioni

Quale di queste cresce più lentamente quando n diventa grande?

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

Che cos'è un algoritmo a forza bruta?

1. AUn algoritmo che gira su molti processori
2. BUn algoritmo che prova tutte le possibili soluzioni candidate
3. CUn algoritmo che tira a indovinare una risposta a caso
4. DUn algoritmo che usa sempre la ricorsione

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

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

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(2ⁿ)
3. CO(n²)
4. DO(log n)

Qual è la complessità temporale di: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

Circa quanti confronti richiede nel caso peggiore la ricerca binaria su un array ordinato di 1,000,000 di elementi?

1. ACirca 100
2. BCirca 500,000
3. CCirca 1,000
4. DCirca 20

Come rileva l'algoritmo di Bellman–Ford un ciclo di peso negativo raggiungibile dalla sorgente?

1. AControlla se qualche arco ha peso negativo
2. BEsegue due volte l'algoritmo di Dijkstra e confronta i due risultati delle distanze
3. CDopo V − 1 turni controlla se qualche arco può ancora essere rilassato
4. DConta i cicli con una visita in profondità

Qual è il tempo di esecuzione dell'algoritmo di Dijkstra con uno heap binario su un grafo con V vertici ed E archi?

1. AO(V³)
2. BO((V + E) log V)
3. CO(V + E)
4. DO(V × E)