« Recherche des deux points les plus rapprochés » : différence entre les versions

En notant <math>n</math> le nombre de points, l'algorithme naïf par [[recherche exhaustive]] a une [[complexité en temps]] en <math>O(n^2)</math>. Il y a en effet <math>\frac{n(n-1)}{2}</math> paires différentes à tester.

 

Il existe un algorithme basé sur [[Diviser pour régner (informatique)|diviser pour régner]] en <math>O(n \log n)</math><ref name=":0">{{Lien web|langue=en|titre=Computational Geometry - An Introduction {{!}} Franco P. Preparata {{!}} Springer|url=https://www.springer.com/kr/book/9780387961316|site=www.springer.com|consulté le=2016-03-25}}</ref>.