Scusate ragazzi potreste spiegarmi questi esercizi?
Assegnata una tabella ordinata di n chiavi, `e vero che ci possono essere algoritmi per la
ricerca con complessit`a minore di O(log(n))?
(a) No, l’algoritmo dicotomico con complessit`a O(log(n)) `e quello ottimo, per cui si ha
θ(log(n)) ;
(b) Si, ad esempio quelli basati su tecniche hash;
(c) Sebbene l’algoritmo dicotomico non sia quello ottimo, non si conoscono algoritmi pi`u
efficienti in nessun caso;
(d) nessuna delle precedenti.
Data una matrice di interi quadrata con n righe, si consideri il problema di verificare se
la somma dei suoi elementi `e uguale ad un intero assegnato. Quale delle seguenti risulta
vera?
(a) Esiste un algoritmo con complessit`a O(log n);
(b) Il problema ha complessit`a Θ(n);
(c) Il problema ha complessit`a Θ(n 2 );
(d) Esiste un algoritmo con complessit`a O(√n);
(e) Nessuna delle precedenti.
Data una stringa di n caratteri, si considerino algoritmi per determinare se essa `e palin-
droma. Cosa si pu`o dire della complessit`a?
(a) Ci sono algoritmi O(
√
n);
(b) Il problema `e Θ(n);
(c) Il problema `e Θ(n 2 );
(d) Nessuna delle precedenti.
