Algoritmo somma esatta

[Cesaropa12]

Esercizio di introduzione agli algoritmi e strutture dati. Pag.32:
Descrivete un algoritmo con Delta di ( n lg n) che, dato un insieme S di n numeri interi e un altro intero x, determini se esistono due elementi in S la cui somma è esattamente x.

[vl4dster]

scusa S e' ordinato? In ogni caso penso che un modo sia: prima lo ordini, e poi parti con un puntatore $x$ al primo elemento e uno $y$ all'ultimo. Se la somma e' piu' piccola di quella che cerchi incrementi $x$, se e' piu' grande decrementi $y$, fino a che $x <= y$.
Se usi un ordinamento basato sui confronti dovrebbe richiedere $O(n*log(n)) + O(n) = O(n*log(n))$, se poi conosci il valore massimo dei valori di S, diciamo $k$, puoi anche ordinare in $O(k)$ e dunque se $k

Cita

Segnala

[Cesaropa12]

Era propio quello che cercavo...Bella idea...Non ho capito perchè se conosco il valore massimo, posso ordinare in $O(k)?

[vl4dster]

Si puo' dimostrare che un qualsiasi algoritmo di ordinamento basato sui confronti non potra' mai scendere sotto O(n lgn), la dimostrazione non e' difficile, quella che conosco io usa l'approsimazione di n! di Stirling e un'albero decisionale in cui i nodi sono i vari confronti che puoi fare in un vettore di n elementi... ma probabilmente c'e' anche nel tuo testo di algoritmi. Ad ogni modo, esistono algoritmi di ordinamento che non si basano sul confronto e che quindi riescono a scendere sotto O(n lgn), pero' richiedono informazioni in piu' sugli elementi del vettore, ad esempio sulla distribuzione(in termini di probabilita') degli elementi. Uno di questi algoritmi e' il counting sort che puo' essere adottato se conosci il valore massimo. L'idea e' quella di scorrere il vettore e contare per ogni elemento $x$ quanti sono gli elementi $<= x$. In questo modo saprai la posizione che x deve avere nell'array ordinato.

Cmq e' piu' difficile a dirsi, sul tuo testo e' sicuramente spiegato meglio