Io non ho ben capito se allo OP serve una disanima teorica sul migliore tra i due algoritmi descritti oppure serve di cercare una soluzione "la più veloce"
anche tra altre possibilità
io, senza una grande trattazione teorica, propenderei per una (consistente) modifica al metodo 1
posto n il numero di punti siamo tutti d'accordo che sia necessario calcolare n*(n-1)/2 distanze, qualunque sia il metodo successivamente usato?
no, non è così, questo è solo il caso peggiore, ma prendiamolo per buono
da questo consegue che la parte di calcolo delle distanze non si può migliorare (poi vediamo anche questo, comunque)
e quindi la sua complessità non mi interessa: si tratta di un fardello che non posso scaricare dalle mie spalle
ma identificare eventuali distanze ripetute si può fare in vari modi, è qui che ho pensato:
lo OP presenta due casi, cito:
Primo metodo: calcolo una distanza, la inserisco nel vettore e controllo che non sia uguale ad una già inserita così in caso positivo posso interrompere il programma senza dover calcolare tutte le distanze.
Secondo metodo: calcolo tutte le distanze e le inserisco nel vettore, poi ordino il vettore usando il merge sort e infine controllo se ci sono valori uguali adiacenti.
se i due metodi fossero cogenti io mi fermo qui,
altrimenti mi permetto di presentare un paio di "migliorie" al metodo 1, migliorie che oserei dire significative
a) inverto l'ordine: calcolo la distanza, controllo che non sia uguale ed eventualmente la inserisco nel vettore
b) tengo il vettore ordinato, cosa che mi permetterà di cercare la prossima distanza calcolata con una ricerca dicotomica invece che con un semplice scorrimento, al prezzo di un continuo "riordinamento parziale" del vettore ho un forte alleggerimento della ricerca
c) quando cerco una distanza, se non la trovo sono almeno già nel punto del vettore dove devo inserirla, questo ammetto sia un po' una banalità, discende del punto b), ma io sono dell'idea che "tutto fa brodo",
ma quella che spero essere la vera differenza è un'altra
d) pre-ordino il vettore dei punti (ok, ok, i vettori delle due coordinate, ma io ragiono come se fosse un singolo vettore di punti)
perché ne effettuo un pre-ordinamento?
ho pensato che la distanza tra due punti è "non maggiore" della somma delle distanze dei due punti dall'origine degli assi
da questo discende che il valore massimo delle distanze è tanto più basso tanto i punti sono vicini all'origine degli assi
da questo discende che la probabilità di trovare distanze basse è tra i punti vicini all'origine... da adesso li chiamo punti "bassi"
se i punti sono distribuiti casualmente la probabilità di avere "doppioni" di distanze (credo, non ho una dimostrazione formale di questo) scende con l'aumentare della distanza dall'origine degli assi (in soldoni: è più facile trovare doppioni se i numeri sono piccoli)
e quindi io testo per primi i punti bassi, sperando che mi vada bene
ultimo (ma poi magari ne trovo ancora) trucco:
tengo traccia del massimo (e magari del minimo) valore finora trovato, con un semplice test "prima" di cominciare la ricerca nell'array so già se per caso ho sforato il massimo, e siccome mi aspetto che i valori (dopo aver pre-ordinato i punti) mi si presentino tendenzialmente in salita (dai punti bassi ai punti alti), spero di poter abbastanza spesso, evitare proprio la ricerca nell'array e limitarmi ad aggiungere in fondo
a dopo per un approccio completamente differente