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 ?
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
Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)
merci beaucoup j’apprécie vraiment votre réponse![]()
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Partager