Scheda di esercizi di Algoritmi e complessità con soluzioni

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

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

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

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

Qual è la complessità temporale della ricerca lineare in un array non ordinato di n elementi (caso peggiore)?

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

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

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

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

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

Qual è la complessità temporale del quicksort nel caso peggiore?

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

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

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

Prendere entrambi gli estremi di ogni arco di un matching massimale dà una copertura dei vertici. Quanto è buona questa copertura?

1. AAl massimo log n volte il minimo
2. BDi qualità ignota rispetto all'ottimo
3. CAl massimo il doppio della dimensione di una copertura dei vertici minima
4. DSempre una copertura dei vertici minima