Scheda di esercizi di Algoritmi e complessità con soluzioni

Un algoritmo O(n) impiega 3 secondi per n = 1 milione. Circa quanto impiega per n = 2 milioni?

1. A6 secondi
2. B3 secondi
3. C12 secondi
4. D9 secondi

Che cosa significa che un'operazione ha tempo O(1)?

1. AIl suo tempo di esecuzione non cresce con la dimensione dell'input
2. BRichiede sempre esattamente un secondo
3. CPuò essere eseguita una sola volta
4. DElabora esattamente un elemento per ogni secondo di tempo di esecuzione

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

1. ACostante
2. BQuadratica
3. CLogaritmica
4. DLineare

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

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

Il limite inferiore per l'ordinamento basato su confronti nel caso peggiore è:

1. AΩ(n)
2. BΩ(n²)
3. CΩ(n log n)
4. DΩ(log n)

Che cosa calcola l'algoritmo di Floyd–Warshall, e con quale velocità?

1. AI cammini minimi da un vertice sorgente a tutti gli altri in O(V + E)
2. BUn albero ricoprente minimo in O(E log V)
3. CUn ordinamento topologico in O(V²)
4. DI cammini minimi tra tutte le coppie di vertici in O(V³)

Il problema dello zaino 0/1 risolto con la programmazione dinamica richiede tempo O(nW). Perché si dice pseudo-polinomiale?

1. APerché l'algoritmo è randomizzato e il suo tempo di esecuzione varia a ogni input
2. BPerché n è sempre piccolo
3. CW è un numero, quindi il tempo è esponenziale nel numero di bit usati per scrivere W
4. DPerché funziona solo per W = 0

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

1. ASì, ma solo per array più corti di 100
2. BNo, perché l'insertion sort non è un ordinamento per confronti
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