6.2.2 : Essayons de limiter le problème
Comme nous l'avons vu, la méthode brute force n'est, a priori, pas une bonne solution à cause de sa complexité.
Mais nous pourions arguer que, du point de vu du temps de calcul, c'est celui de l'interaction qui prend du temps et comme celle-ci evolue en $\frac{1}{r^2}$
avec $r$
la distance entre deux particules, nous pourions mettre une limite sur $r$
afin de ne pas calculer les interactions des particules qui se trouvent trop loin.
Sauf que... dans ce cas là, c'est la complexité du calcul qui permet de savoir si on doit calculer l'interaction entre deux particules qui pose problème. Comme cette complexité varie elle aussi en $O\left(N^2\right)$ , le temps de calcul, bien que plus faible, finira lui aussi par devenir un problème.
Comme l'a dit le Confucius du calcul haute performance :
Le calcul le plus rapide est celui que l'on ne fait pas.
Confucius du calcul haute performance
Il nous faudrait donc, un moyen de ne pas faire ce calcul de test et d'avoir directement les bonnes particules sur lesquelles calculer les interactions.
Ce qui implique une phase de tri.