Comment déterminer la complexité de l'algorithme de Clarke et Wright ?

Bonjour,

1. On regarde là où il y le plus de boucles imbriquées. Attention, si dans une boucle on appelle une fonction qui a elle-même un ou des boucles, elles comptent dans les imbrications à prendre en compte.

2. On ne garde que les ordres supérieurs : si un algorithme a une étape en O(n²) et une étape en O(n log n) on gardera O(n²).

Étapes

• Dans le cas présent, le tableau des gains associe dans 2 boucles n points à (n-1) points soit n(n-1) soit O(n²) dixit règle 2.
• Ensuite ils sont triés , un tri rapide est en O(p log p). Ici p = n(n-1) aussi p log p = n(n-1).log( n(n-1) ). Alors O( n(n-1).log( n(n-1) ) ) = O(n² log(n² - n ) ) - log(n²-n) ) = O( n² log( n² ) ) = O( 2 n² log(n) ) = O(n² log n ). Tout ce qui est barré l'est au titre de la règle 2.
• Ensuite, on affecte les sommets ce qui est en O(n).

On ne garde que le degré le plus élevé soit O(n² log n) qui est la complexité de cet algorithme.

Salutations