Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

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


Sujet :

Algorithmes et structures de données

  1. #1
    Nouveau Candidat au Club
    Comment déterminer la complexité de l'algorithme de Clarke et Wright ?
    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 ?

  2. #2
    Membre éclairé
    Complexité
    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
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

  3. #3
    Nouveau Candidat au Club
    merci beaucoup j’apprécie vraiment votre réponse