PDA

Visualizza la versione completa : Complessitā computazionale


sheva7
17-08-2012, 16:37
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.

alka
17-08-2012, 18:36
Il forum non č un servizio di reclutamento volontari per la risoluzione dei compiti a casa.

Leggi il Regolamento (http://forum.html.it/forum/showthread.php?s=&threadid=973887).

Loading