Esercizio di descrizione di un algoritmo.
Giulio Petrucci
come "decompressione" al lavoro, ho iniziato a risolvere esercizi presi
da alcuni libri di algoritmi e strutture dati. Ora, mi trovo davanti a
questo quesito.
Dato un insieme S di N interi (che possiamo assumere come fisso e
ordinato), descrivere un algoritmo che abbia costo computazionale Teta(N
* Log_2(N)) che, dato un intero x, determini se l'insieme contiene
almeno una coppia di elementi (a,b) tali che a + b = x.
La mia proposta di soluzione è:
1] for i = 0 .. N - 1:
2] a = S[i];
3] diff = x - a;
4] ricerca binaria di diff in S[i+1..N-1]
5] se la ricerca va a buon fine ritorna (a, b)
Il problema è che non riesco a dimostrare che effettivamente il costo
computazionale sia quello richiesto. :-) Il contenuto di un passo del
ciclo for ha costo pari al costo della ricerca binaria che è Log_2(N-i).
Questo costo va ripetuto N volte (ossìa il numero di passi del ciclo
for). Basta questo per dire che, di fatto, a per N --> infinito il costo
di questo algoritmo è quello richiesto dal problema?
Grazie,
Giulio
--