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