J'ai utilisé l'heuristique de Clarke and Wright nommé méthode des distances sauvées.Je veux savoir comment déterminer la complexité de cet algorithme ?
Version imprimable
J'ai utilisé l'heuristique de Clarke and Wright nommé méthode des distances sauvées.Je veux savoir comment déterminer la complexité de cet algorithme ?
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(2n² 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
merci beaucoup j’apprécie vraiment votre réponse :lol: