Scheda di esercizi di Algoritmi e complessità con soluzioni

Un ciclo parte con i = 1 e raddoppia i a ogni iterazione finché i > n. Quante iterazioni esegue?

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

Qual è la complessità temporale nel caso migliore dell'insertion sort, su un array già ordinato?

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

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

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

La complessità temporale del Fibonacci ricorsivo ingenuo (fib(n) = fib(n−1) + fib(n−2)) è:

1. ALineare
2. BEsponenziale
3. CLogaritmica
4. DCostante

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

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

Quale affermazione su una funzione ricorsiva senza un caso base raggiungibile è corretta?

1. AIl compilatore la trasforma sempre in un ciclo che termina in modo sicuro
2. BViene eseguita in tempo O(1)
3. CRestituisce automaticamente 0
4. DContinua a chiamare se stessa finché lo stack delle chiamate va in overflow

Il problema della fermata dimostra che:

1. AAlcuni programmi girano più velocemente su computer più veloci, quindi la terminazione dipende dall'hardware
2. BOgni programma prima o poi si ferma
3. CI cicli andrebbero evitati
4. DNessun algoritmo può decidere, per ogni programma e ogni input, se il programma si ferma

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, il limite inferiore si applica al caso peggiore su tutti gli input, non a ogni input
2. BNo, perché l'insertion sort non è un ordinamento per confronti
3. CSì, ma solo per array più corti di 100
4. DSì, quindi il limite inferiore è sbagliato