1. #1
    Membre à l'essai
    Étudiant
    Inscrit en
    novembre 2009
    Messages
    38
    Détails du profil
    Informations personnelles :
    Âge : 29

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : novembre 2009
    Messages : 38
    Points : 24
    Points
    24

    Par défaut Complexité d'un algorithme de tri

    Bonjour !

    J'ai un exercice qui est le suivant :

    On cherche à trier un tableau de n entiers dont seulement p éléments ne sont pas à leur place (si on retire ces p éléments, les n-p restants sont bien dans l'ordre). Quelle est la complexité au pire des cas d'un tri par insertion sur un tel tableau ? Justifier votre réponse.

    Je suis débutante en algorithme et notion de complexité. Quelqu'un peut-il me proposer une solution ou me mettre sur le bon chemin pour comprendre la notion de complexité de tri des tableaux ? Merci d'avance !

  2. #2
    Responsable Delphi

    Avatar de gvasseur58
    Homme Profil pro
    Cultivateur de code (bio)
    Inscrit en
    février 2013
    Messages
    1 059
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Isère (Rhône Alpes)

    Informations professionnelles :
    Activité : Cultivateur de code (bio)
    Secteur : Enseignement

    Informations forums :
    Inscription : février 2013
    Messages : 1 059
    Points : 12 514
    Points
    12 514
    Billets dans le blog
    33

    Par défaut

    Bonjour,

    Le problème est celui-ci : les tris doivent être rapides afin d'immobiliser le moins longtemps possible la machine et l'utilisateur. On ne calcule pas en temps (car dépendant de la machine), mais en opérations à effectuer. Ici, l'opération de base est la comparaison des entiers du tableau. Afin de calculer la complexité du tri, on se place dans le pire des cas

    Si je dois insérer un M-ième élément dans mon tableau, je vais devoir au pire comparer mon nouvel entier avec tous ceux déjà triés, soit M-1 éléments. J'aurai alors M éléments après l'insertion.
    Si j'en insère un autre, je devrais cette fois-ci balayer, au pire, M éléments pour en obtenir M+1...
    Je boucle ainsi jusqu'au dernier élément à insérer. Le nombre de comparaisons a toujours un temps de retard sur le nombre d'éléments triés.
    SI j'avais commencé par un élément, j'aurais donc effectué :
    Total = 1 + 2 + 3 + ... + M-2 + M-1 comparaisons.
    On sait que cette somme peut s'écrire M-1 + M-2 + M-3 + ... + 2 + 1 = Total.

    On a donc, en additionnant les deux :
    2 Total = M + M + M + ... + M + M [=> M-1 fois]
    Donc Total = M (M-1)/2
    Sachant que M(M-1) est proche de M² si M est très grand et que le rapport /2 n'a pas de sens pour deux ordinateurs aux vitesses différentes, on dira que l'ordre de complexité du tri est M².

    Ce n'est pas la réponse au problème, mais le principe devrait y être. Un vrai mathématicien devrait affiner le raisonnement et le rendre plus rigoureux

    Cordialement
    Accès à mon site et à mon blog. Actualités, cours et ressources Delphi, Lazarus et Pascal.
    Pensez à la balise - Quelqu'un vous a aidé ou vous appréciez une intervention ? Pensez au

  3. #3
    Membre confirmé

    Profil pro
    Inscrit en
    juillet 2009
    Messages
    103
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : juillet 2009
    Messages : 103
    Points : 499
    Points
    499

    Par défaut

    Le pire des cas est si les éléments doivent etre remontés par les autres éléments.

    Donc par exemple, que les éléments déja triés soient les plus grands, mais qu'ils soient au début du tableau. Ou bien qu'ils soient les plus petits et qu'ils soient a la fin du tableau. Et pour les éléments additionnels qu'ils soient en ordre décroissant.

    Si les éléments déja triés sont tous traversés, cela donne n-p comparaison pour chaque élément additionnel, donc (n-p)*p pour traverser les éléments déja triés.

    Pour le tri des éléments supplémentaires entre eux, s'ils sont en ordre décroissant, cela ajoute 1+2+3...+(p-2)+(p-1) = p*(p-1)/2

    Enfin pour les éléments déja triés, il faut ajouter 1 pour chacun, donc cela ajoute n-p ou pour etre exact max(n-p-1,0)

    Donc un total de:

    (n-p)*p + p*(p-1)/2 + n-p

    ce qui donne n si p = 0
    et donne p*(p-1)/2 si p = n
    Par-delà nos conceptions du bien et du mal se trouve une prairie. Je te rencontrerai là-bas.

Discussions similaires

  1. Complexité de l'algorithme de Tri Fusion
    Par judge06 dans le forum Général Algorithmique
    Réponses: 10
    Dernier message: 26/03/2007, 22h04
  2. Probleme avec mon algorithme de tri
    Par kaygee dans le forum Fonctions
    Réponses: 6
    Dernier message: 09/01/2006, 21h23
  3. Réponses: 16
    Dernier message: 10/11/2005, 22h51
  4. complexité d'un algorithme par un...algorithme??
    Par afrikha dans le forum Général Algorithmique
    Réponses: 5
    Dernier message: 02/11/2005, 00h59
  5. algorithme de tri tableau :afficher que les éléments unique
    Par sofiane61 dans le forum Général Algorithmique
    Réponses: 19
    Dernier message: 31/03/2005, 19h50

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