Extraction de valeurs - matrice des distances

Citation:

---

Envoyé par mchk0123

@souviron34

Le seul argument pour dire que ton programme est plus rapide est qu'il réussise à faire un "early break" (fin de programme trés tôt via la condition encadrant ton "break").

Seulement voilà, même avec un tri de tes ensembles A et B selon l'axe des X (pourquoi X d'ailleurs ?), qu'est ce qui te dit que le tout dernier point n'est pas le plus proche ? Auquel cas -> temps moyen = O(N * n * ).

Mon algorithme approché que j'ai donné est imbatable est terme de performances.

---

non ce que je disais pour les tris dans le dernier post était les VRAIES distances.....

à chaque point : tu calcules les vraie distances, et un qsort.

mais bon....

je vais pas me battre ;) :lol:

Autre idée que j'ai implémentée avec succès dans une appli opérationnelle :
(mais moi je comparais avec une distance donnée) :

prendre l'ensemble des points N1 et N2 (faire une structure par exemple X,Y,numéro)


les trier en X (qsort) O(log(N1+N2))

pour chaque point en partant de 0 :

si point de 1 :
partir symétriquement à gauche et à droite
dès que npts de 2 = 10 et distance en X supérieure à distance[9] sortir

[EDIT]

Complexité totale :

le tri fait, en général (en gros) on aura N1 * 20 ou 30 calculs de distance

Donc en gros O(log(N1+N2)) + N1*30

Et on peut accélerer en stockant au fur et à mesure l'indice du dernier point de 2 à gauche pris en compte pour le dernier point de N1, qui limitera l'exploration à gauche.

[/EDIT]