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 :

Calculer la complexité d'un algorithme


Sujet :

Algorithmes et structures de données

  1. #21
    Expert éminent sénior
    Citation Envoyé par b_reda31 Voir le message
    En termes de temps d'exécution,Oui. Mais en terme de complexité en O(.) c'est négligeable.
    c'est surtout que la définition de la complexité est par rapport une valeur considérée comme paramètre

    Les "opérations" simples (telles que fnpour etc) ne sont en général pas considérée comme des paramètres...

    Dans un calcul de complexité en général, on évalue par rapport à la taille d'un élément entrant caractéristique...

    Il y a un seul cas je crois (je ne me souviens plus du nom) où l'on veut calculer la complexit en termes d'opérations élémentaires...

    Le cas général est donc par rapport à la taille du paramètre d'entrée..

    Par exemple, dans le quicksort, bien évidemment on calcule la complexité par rapport au nombre d'éléments à trier..
    "Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".

    Consultant indépendant.
    Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
    C, Fortran, XWindow/Motif, Java

    Je ne réponds pas aux MP techniques

  2. #22
    Membre régulier
    Bonjour,

    Comme expliqué précédemment, le paramètre joue beaucoup sur ton calcul de complexité, tu peux comparer le nombre d’accès à un tableau, le nombre d'itération de tes boucles, le nombre de comparaison (if), nb d'appel de fonctions.. etc.

    Généralement tu calcules une compléxité pour comparer deux algo qui font la même chose.

    Ce calcul se fait de 3 façons différentes, le calcul de la compléxité dans le pire des cas, dans le meilleurs des cas et la compléxité moyenne.

    Quand tu compares deux algo il faut s'assurer de partir sur la même base de comparaison.
    Pour les algo un peu complexe, c'est le nombre d'itération des boucles qui va jouer beaucoup, ou appel de fonction si algo récursive.


    David.
    Cordialement,

    David.

  3. #23
    Membre à l'essai
    Citation Envoyé par b_reda31 Voir le message
    Code C :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
     
    seq1:
    i=1
    while(i<n) do
    {
    i=2*i;
    op;
    }
    MaSol:T(n)=O(n)

    Je ne pense pas que Seq1 soit O(n),pour voir ça il suffit de le dérouler avec un exemple.
    Ici j’ai pris le cas particulier ou n=8

    i = 1 = 2^0 --------&#61664; 1 exécution de « op »
    i = 2 = 2^1 --------&#61664; 1 exécution de « op »
    i = 4 = 2^2 --------&#61664; 1 exécution de « op »
    i = 8 = 2^3 --------&#61664; Fin de la condition de la boucle.

    Pour n=8,l’opération « op » s’est exécutée 3 fois,à travers l’exemple on peut déduire que d’une manière générale l’opération « op » s’exécute « k » fois tel que 2^(k-1)<n<=2^k
    Dans le meilleurs des cas on a n=2^k donc k=Log2 n
    Donc T(n) = Log2 n.

    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
     
    seq2:
    for i=1 to n do
    j=1
    while(j<n) do
    j=2*j;
    op;
    end while
    end for
    MaSol: T(n)=O(n.log(n))


    Ici Seq1 est exécuté n fois donc ça m'a l'air correcte. T(n) = O(n Log2 n).
    SVP, dites moi comment vous avez trouvé n(log2^n) ??
    Moi j'ai trouvé log(2^n) parce que pour n=8, la deuxième boucle s'exécute 3 fois, donc c'est comme le seq1 non ?!

  4. #24
    Modérateur

    Citation Envoyé par lyess Voir le message
    SVP, dites moi comment vous avez trouvé n(log2^n) ??
    Moi j'ai trouvé log(2^n) parce que pour n=8, la deuxième boucle s'exécute 3 fois, donc c'est comme le seq1 non ?!
    La deuxième boucle se trouve dans la première.
    Consignes aux jeunes padawans : une image vaut 1000 mots !
    - Dans ton message respecter tu dois : les règles de rédaction et du forum, prévisualiser, relire et corriger TOUTES les FAUTES (frappes, sms, d'aurteaugrafe, mettre les ACCENTS et les BALISES) => ECRIRE clairement et en Français tu DOIS.
    - Le côté obscur je sens dans le MP => Tous tes MPs je détruirai et la réponse tu n'auras si en privé tu veux que je t'enseigne.(Lis donc ceci)
    - ton poste tu dois marquer quand la bonne réponse tu as obtenu.

  5. #25
    Membre à l'essai
    Calcul de Complexité
    SVP, comment peut-on calculer la Complexité de cet Algorithme:

    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    Algo()
    {
     
        i=1
        while(i<n) do
            i=2*i;
            for j=1 to i do
                <operation>;
            end for
        end while
     
    }


    Merci d'avance.

  6. #26
    Membre éprouvé
    Il ne faut pas hésiter à faire le déroulement de l'algorithme en prenant plusieurs valeurs pour n. De cette façon vous allez pouvoir y voir plus clair.

    Prenons l'exemple où n = 8 :

    Etant donnée qu'on cherche à calculer la complexité asymptotique, on se limitera au calcul du nombre de fois que l'instruction <Op> est exécutée.


    • i = 1<n
      • i = i * 2 = 2
        • j = 1 <operation>

        • j = 2 <operation>




    • i = 2<n
      • i = i * 2 = 4
        • j = 1 <operation>

        • j = 2 <operation>

        • j = 3 <operation>

        • j = 4 <operation>




    • i = 4<n
      • i = i * 2 = 8
        • j = 1 <operation>

        • j = 2 <operation>

        • j = 3 <operation>

        • j = 4 <operation>

        • j = 5 <operation>


        • j = 6 <operation>


        • j = 7 <operation>


        • j = 8 <operation>




    Dans notre exemple, l'opération est exécutée 2 + 4 + 8 fois. Et dans un cas général on a : 2 + 4 + 8 + 16 + . . . + m
    Tel que m est la plus petite puissance de 2 supérieure ou égale à n.
    Dans le meilleur des cas on a m = n :
    2 + 4 + 8 + ... + n.
    C'est donc la somme des terme d'une suite géométrique à raison égale à 2.


    le nombre de terme k représente le degré de puissance de n. soit k = log2(n).
    (dans notre exmple k = 3, si on avait n = 16 ==> k = 4...etc).
    En appliquant la formule de la suite, on obtient alors une complexité linéaire O(n).
    « Il est assez difficile de trouver une erreur dans son code quand on la cherche. C’est encore bien plus dur quand on est convaincu que le code est juste!!»

  7. #27
    Membre à l'essai
    Calcul de Complexité
    Merci beaucoup pour votre gentil retour.
    Oui j'ai déroulé l'algorithme sauf que je me suis bloquée au niveau de la borne supérieure de la somme...

    D'après ce que j'ai compris, la formule finale de la somme est la suivante:
    &#8721;(2^k) tel que: k varie de 1 à Log2(n)

    N'est ce pas?

  8. #28
    Membre éprouvé
    Citation Envoyé par lyess Voir le message

    D'après ce que j'ai compris, la formule finale de la somme est la suivante:
    &#8721;(2^k) tel que: k varie de 1 à Log2(n)

    N'est ce pas?
    Oui, dans le cas où "n" est une puissance de deux (n = 2^k). C'est d'ailleurs le meilleur des cas.
    Le pire des cas se produit lorsque "n" est de la forme (2^k) + 1... si je ne me trompe pas ...on aurait ici : &#8721;(2^k) tel que: k varie de 1 à Log2(m) où m est la plus petite puissance de 2 supérieure à n.
    Mais dans les deux cas l'algo est en O(n)... sauf erreur de ma part
    « Il est assez difficile de trouver une erreur dans son code quand on la cherche. C’est encore bien plus dur quand on est convaincu que le code est juste!!»

  9. #29
    Membre à l'essai
    Merci beaucoup! Bonne journée.

  10. #30
    Membre à l'essai
    bonjour merci la description des séquences de complexité précédente bon j'ai cette séquence si possible de m'aider à calculer sa complexité
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    i &#8592; 1
    FOR k &#8592; 1 TO n DO
      i &#8592; 2*i
      FOR L &#8592; 1 TO i DO
        FOR m &#8592; 1 TO k DO
          Opération ;
        END-FOR
      END-FOR
    END-FOR

  11. #31
    Rédacteur/Modérateur

    Tout d'abord, il est (fortement) recommandé d'indenter son code. C'est beaucoup plus lisible.
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    i &#8592; 1
    FOR k &#8592; 1 TO n DO
      i &#8592; 2*i
      FOR L &#8592; 1 TO i DO
        FOR m &#8592; 1 TO k DO
          Opération ;
        END-FOR
      END-FOR
    END-FOR


    L'exemple est simple. On remarque qu'il y a 3 boucles imbriquées. Et il faut sans doute supposer que Opération s'effectue en temps constant. Le but est donc de déterminer le nombre d'itérations pour chacune des boucles et de les multiplier entre elles puisqu'elles sont imbriquées.
    • Combien d'opérations x pour la boucle FOR k ?
    • Combien d'opérations y pour la boucle FOR l ?
    • Combien d'opérations z pour la boucle FOR m ?


    Connaissant x, y et z, le produit de ces nombres x * y * z te donnera la complexité de l'algorithme en fonction d'un nombre d'opérations N.

    La seule petite difficulté de cet exemple réside dans le calcul du nombre d'opérations z de la boucle FOR m. Il faudra faire un peu de dénombrement, mais rien de bien méchant à priori.

    Bon courage.
    Tutoriels et FAQ TypeScript

  12. #32
    Membre à l'essai
    merci pour votre réponse ; pour mon cours je pense que se sera ordre de N à la puissance trois car X et Z vont êtres N fois alors que Y est N/2 donc sera O(N)*O(N/2)*O(N)=O(N^3) n'est ce pas ou c'est faux

  13. #33
    Rédacteur/Modérateur

    Ce n'est pas exact.
    Pour s'en convaincre, le mieux est de faire des tests avec différentes valeurs de N.
    Tutoriels et FAQ TypeScript

  14. #34
    Membre à l'essai
    bonsoir j'ai vérifié encore donc la deuxième boucle d'ordre deux seulement donc pour n=4
    k=1
    i=2
    l=1....donc m=1 une première opération
    l=2....donc m=2 une deuxième opération ça fait 2 op

    k=2
    i=2
    l=1 donc m=1 et m=2 donc 2op
    l=2 donc m=1 et m=2 donc 2op ça fait 4 op

    k=3
    i=2
    l=1 donc m=1 et m=2 et m=3 donc 3op
    l=2 donc m=1 et m=2 et m=3 donc 3op ça fait 6 op

    k=4
    i=2
    l=1 donc m=1 et m=2 et m=3 et m=4 donc 4op
    l=2 donc m=1 et m=2 et m=3 et m=4 donc 4op ça fait 8op
    alors
    la somme 2+4+6+8=20op pour n=4 donc c'est de l'ordre de O(n^2)

    j'attends votre remarque et merciii

  15. #35
    Rédacteur/Modérateur

    Ca me semble pas trop mal.
    Il faudrait démontrer plus formellement ton hypothèse.
    Je t'invite à lire les précédents posts pour voir comment t'y prendre.
    On peut utiliser les séries ou les dénombrements, ça revient au même.
    Tutoriels et FAQ TypeScript