Etude de complexité

La recherche du point frontière décrite au programme 2.1 nécessite un parcours complet de la liste définissant la frontière soit pour chaque recherche une complexité linéaire par rapport à la taille de cette liste. Cette recherche est réalisée pour chaque « masse ». Le déplacement d'un point nécessite donc autant d'appels à la fonction pt_front que de données.

Soit : $f$ le nombre de points définissant la frontière ;

       $d$ le nombre de « masses », ie le nombre de données ;

       $n$ le nombre de points à déplacer.

Alors, on obtient une complexité pour le programme final, en notant $C(f)$ la complexité de la fonction pt_front :

$$n\,d\,C(f)$$

avec : $C(f) = \mathrm{O}(f)$