IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
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
    Homme Profil pro
    Collégien
    Inscrit en
    mai 2020
    Messages
    2
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 26
    Localisation : Tunisie

    Informations professionnelles :
    Activité : Collégien

    Informations forums :
    Inscription : mai 2020
    Messages : 2
    Points : 1
    Points
    1
    Par défaut 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 éprouvé

    Homme Profil pro
    Directeur de projet
    Inscrit en
    mai 2013
    Messages
    335
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet
    Secteur : Service public

    Informations forums :
    Inscription : mai 2013
    Messages : 335
    Points : 1 188
    Points
    1 188
    Par défaut 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
    Homme Profil pro
    Collégien
    Inscrit en
    mai 2020
    Messages
    2
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 26
    Localisation : Tunisie

    Informations professionnelles :
    Activité : Collégien

    Informations forums :
    Inscription : mai 2020
    Messages : 2
    Points : 1
    Points
    1
    Par défaut
    merci beaucoup j’apprécie vraiment votre réponse

Discussions similaires

  1. Comment déterminer son tarif quand on est Freelance ?
    Par nolwenn dans le forum Freelance
    Réponses: 20
    Dernier message: 27/03/2015, 12h05
  2. Comment déterminer la fin d'un message sur le port serie ?
    Par zeddy23 dans le forum Composants VCL
    Réponses: 2
    Dernier message: 11/01/2005, 06h12
  3. Comment déterminer l'espace disque de tous les lecteurs
    Par ZeKudjat dans le forum MS SQL Server
    Réponses: 3
    Dernier message: 05/01/2005, 16h19
  4. Réponses: 2
    Dernier message: 06/07/2004, 18h46
  5. Comment déterminer si un composant est d'un type "TMonT
    Par DanielR dans le forum C++Builder
    Réponses: 2
    Dernier message: 20/03/2004, 19h22

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo