Data una sequenza di numeri reali A e un numero reale x, scrivere un algoritmo che stampi tutte le coppie di numeri la cui somma è x. Questo algoritmo deve avere complessità O(nlogn).
Grazie a chiunque mi aiuterà!
Saluti.
Algoritmo e complessità
-
MindFlyer
-
MindFlyer
Se i numeri sono interi e A è finito, un'idea potrebbe essere questa.
Metti A in ordine crescente in tempo O(nlogn), ad esempio con il quicksort.
Per ogni y in A tale che 2y<=x (O(n)), cerca in A l'elemento z=x-y (in O(logn) con la ricerca binaria). Se lo trovi aggiungi la coppia (y,z) all'output.
Metti A in ordine crescente in tempo O(nlogn), ad esempio con il quicksort.
Per ogni y in A tale che 2y<=x (O(n)), cerca in A l'elemento z=x-y (in O(logn) con la ricerca binaria). Se lo trovi aggiungi la coppia (y,z) all'output.
Ultima modifica di MindFlyer il 08 ott 2006, 20:20, modificato 2 volte in totale.
-
MindFlyer
