Write psuedocode to determine the number of pairs of values in an input file that are equal. If your first try is quadratic, think again and develop a linearithmic solution.
Ho trovato questa domanda in un libro di testo e non sono sicuro di come scrivere questo algoritmo. La mia ipotesi iniziale è stata quella di scriverlo lungo la formula nC2 = (n (n + 1)) / 2. Qualsiasi aiuto è apprezzato.
Non voglio darti il codice ma alcuni suggerimenti. La prima cosa da prestare attenzione è che l'esercizio richiede soluzioni linearitmiche. Ciò significa che l'algoritmo potrebbe consumare il tempo N log (N) da eseguire dove N è il numero di voci (valori nel file nel tuo caso).
Quindi la struttura di base dell'algoritmo necessario sembra essere un ciclo attraverso tutte le voci e una ricerca binaria all'interno del ciclo. Per fare una ricerca binaria hai bisogno di una voce ordinata, quindi ordinala. Alla fine il tuo algoritmo potrebbe sembrare qualcosa del tipo:
Leggi altre domande sui tag algorithms