Complexité

Cet algorithme base sur une stratégie a essais successifs "à trous" repose sur le principe suivant : pour tracer toutes les triangulations, il va essayer toutes (presque) les combinaisons de cordes parmi les M cordes traçables dans le polygone, une corde étant tracée ou non. Cela nous amène à une complexité de l'algorithme en terme d'appels récursifs majorée par :

$$T(M) = 2^m$$

Je dis bien "majorée", car en réalité, l'algorithme ne calcule pas toutes les combinaisons.

D'autre part, comme observe précéda-ment, le nombre de cordes traçables dans un polygone a N sommets est :

$$M = \frac{N * (N -3 )}{2}$$

.

Ce qui nous ramené à une formule de complexité égale à :

$$T(N) = 2^{ \frac{N *(N-3)}{2}}$$

$$\Longrightarrow Complexite\in\Theta ( 2^{n^2} )$$

La complexité obtenue est dramatiquement démesurée, et rend ce programme inutilisable même pour un polynome de taille moyenne. Il nous faut donc trouver une autre méthode...