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 :

[Complexité d'un algorithme] Triangle de Sierpinski


Sujet :

Algorithmes et structures de données

  1. #1
    Membre du Club
    Profil pro
    Étudiant
    Inscrit en
    Septembre 2006
    Messages
    112
    Détails du profil
    Informations personnelles :
    Âge : 37
    Localisation : Belgique

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Septembre 2006
    Messages : 112
    Points : 58
    Points
    58
    Par défaut [Complexité d'un algorithme] Triangle de Sierpinski
    Bonjour,

    J'ai écrit un programme qui donne une représentation du triangle de Sierpinski dans une matrice n*n (n étant une puissance entière positive de 2). Les trous sont représentés par des caractères, les vides par des espaces, voici le code (c'est du C++ mais ça n'est pas bien méchant il n'y a que des boucles en gros) :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
     
         int X = n;
     
         while (X > 1)
         {
               for (int i = 0; i < n; i+= X)
               {
                   for (int j = 0; j < n; j+= X)
                   {
                       for (int k = 0; k < X/2; k++)
                       {
                           for (int l = 0; l < X/2; l++)
                           {
                               C[i + k][j + X/2 + l] = ' ';
                           }
                       }
                   }
               }
               X = X/2;
         }
    Bon. Maintenant j'aimerais bien évaluer la complexité en fonction de n (en terme de grand O) de cet algorithme

    Quelqu'un se sent d'attaque ? Moi j'ai essayé d'évaluer ça et je tombe sur une complexité en O(n^4)
    Pour ce faire j'ai "simplement" évaluer la nombre de fois que chaque boucle for s'executait en fonction de n mais je pourrais bien m'être trompé

    Quelqu'un sait-il me dire si c'est plausible/correcte ?

    merci

  2. #2
    Membre éclairé
    Inscrit en
    Janvier 2005
    Messages
    711
    Détails du profil
    Informations forums :
    Inscription : Janvier 2005
    Messages : 711
    Points : 751
    Points
    751
    Par défaut
    a mon avis, c'est beaucoup moins que ca. comment rentre tu les caracteres ?? on ne voit que les espaces..

  3. #3
    Membre éclairé
    Inscrit en
    Janvier 2005
    Messages
    711
    Détails du profil
    Informations forums :
    Inscription : Janvier 2005
    Messages : 711
    Points : 751
    Points
    751
    Par défaut
    le bout que tu nous donnes est en O(log(n)*n^2/4), a priori.

  4. #4
    Membre du Club
    Profil pro
    Étudiant
    Inscrit en
    Septembre 2006
    Messages
    112
    Détails du profil
    Informations personnelles :
    Âge : 37
    Localisation : Belgique

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Septembre 2006
    Messages : 112
    Points : 58
    Points
    58
    Par défaut
    comment rentre tu les caracteres ?? on ne voit que les espaces..
    Ah ça peut importe j'ai une matrice de caractère et je veux transformer cette dernière en une représentation du triangle de Sierpinski

    Bon je vais essayer de comprendre ce que tu me donnes comme complexité, merci

  5. #5
    Membre éclairé
    Inscrit en
    Janvier 2005
    Messages
    711
    Détails du profil
    Informations forums :
    Inscription : Janvier 2005
    Messages : 711
    Points : 751
    Points
    751
    Par défaut
    si ca t'interresse, voila comment je trouve ca :

    si n=2^k, la boucle while principale efectue k tour, cad log2(n) (log en base 2).

    concernant les 4 boucles a l'interieur, pour un X donné : les 2 premieres boucles vont de 0 a n par pas de X, donc tournent n/x fois chacune, les 2 suivantes vont de 0 a x/2 par pas de 1, donc tournent X/2 fois chacune. au total :

    log2(n) * n/X * n/X * X/2 *X/2 = log2(n) * n^2 *(n^2)/4

  6. #6
    Membre du Club
    Profil pro
    Étudiant
    Inscrit en
    Septembre 2006
    Messages
    112
    Détails du profil
    Informations personnelles :
    Âge : 37
    Localisation : Belgique

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Septembre 2006
    Messages : 112
    Points : 58
    Points
    58
    Par défaut
    Ah merci bien d'avoir détaille le calcul

    J'ai une grosse question, comment calculerais-tu la complexité du code suivant (X est supposé être une puissance entière de 2, disons 2^l pour fixé les idées) :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
     
     
    while (X > 1)
    {
         for (int i = 0; i < X/2; i++)
         {
              // Instructions en O(1) ...
         }
         X = X/2;
    }
    ?

    Moi j'essaie d'évaluer immédiatement le nombre de fois que la boucle for s'execute c'est à dire :

    2^(l - 1) + 2^(l - 2) + 2^(l - 3) + ... 1 = (Somme de k allant de 1 à l) de (2^l / 2^k)

    Après calcule de cette somme par une petite formule de math ça me donne 2^(l) - 1 soit une complexité en O(n)

    Je me trompe ?

    merci

  7. #7
    Membre éclairé
    Inscrit en
    Janvier 2005
    Messages
    711
    Détails du profil
    Informations forums :
    Inscription : Janvier 2005
    Messages : 711
    Points : 751
    Points
    751
    Par défaut
    si ta formule de maths est juste, ca doit etre ca...

  8. #8
    Membre éclairé
    Inscrit en
    Janvier 2005
    Messages
    711
    Détails du profil
    Informations forums :
    Inscription : Janvier 2005
    Messages : 711
    Points : 751
    Points
    751
    Par défaut
    en faisant un petit test avec n=1024, je trouve 2046 operations.. donc ca a l'air d'etre du O(2n), donc du O(n). ca m'a l'air bon !

  9. #9
    Membre du Club
    Profil pro
    Étudiant
    Inscrit en
    Septembre 2006
    Messages
    112
    Détails du profil
    Informations personnelles :
    Âge : 37
    Localisation : Belgique

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Septembre 2006
    Messages : 112
    Points : 58
    Points
    58
    Par défaut
    Oui j'ai utilisé la formule (il n'est pas possible d'utiliser Latex sur le forum ?)

    (Somme pour k allant de 0 à n) x^k = (1 - x^(n + 1))/(1 - x)

    Mais moi c'est ce même raisonnement que j'ai appliqué pour chacune des boucles donc ça me donne pour chaqune des 4 boucles for une complexité en O(n) donc j'ai à chaque fois multiplier ce qui me donne de l'O(n^4)

    Je me trompe peut-être bien mais je ne vois pas pourquoi

    merci

  10. #10
    Membre du Club
    Profil pro
    Étudiant
    Inscrit en
    Septembre 2006
    Messages
    112
    Détails du profil
    Informations personnelles :
    Âge : 37
    Localisation : Belgique

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Septembre 2006
    Messages : 112
    Points : 58
    Points
    58
    Par défaut
    Mais ça ne peut pas etre bon vu que j'ai testé avec différentes valeurs de n et n^4 c'est beaucoup trop

    merci

  11. #11
    Membre du Club
    Profil pro
    Étudiant
    Inscrit en
    Septembre 2006
    Messages
    112
    Détails du profil
    Informations personnelles :
    Âge : 37
    Localisation : Belgique

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Septembre 2006
    Messages : 112
    Points : 58
    Points
    58
    Par défaut
    le bout que tu nous donnes est en O(log(n)*n^2/4), a priori.
    J'ai testé et c'est exactement ça (chapeau ) mais je ne comprends paaaaass pourquoi ma solution est fausse

    merci !

  12. #12
    Membre du Club
    Profil pro
    Étudiant
    Inscrit en
    Septembre 2006
    Messages
    112
    Détails du profil
    Informations personnelles :
    Âge : 37
    Localisation : Belgique

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Septembre 2006
    Messages : 112
    Points : 58
    Points
    58
    Par défaut
    Je pense que vu la manière dont X varie je ne peux pas simplement multiplier le nombre d'itérations de chaque boucle entre elles

    Par exemple pour :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
     
     int X = n;
     
         while (X > 1)
         {
                       for (int k = 0; k < X/2; k++)
                       {
                           for (int l = 0; l < X/2; l++)
                           {
                               // truc en O(1)
                           }
               }
               X = X/2;
         }
    Le nombre de fois que le truc en O(1) est éxécuté est (n/2)^2 + (n/4)^2 + (n/8)^2 + ... ce qui au final donne (n² - 1)/3 executions (ça reste en O(n²) mais si on test sur de petites valeurs de n on ne s'en rend pas compte vu que la différence entre n² et (n² - 1)/3 est grande)
    Il faudrait que je refasse le même calcul pour les deux autres boucles ...

  13. #13
    Membre éclairé
    Inscrit en
    Janvier 2005
    Messages
    711
    Détails du profil
    Informations forums :
    Inscription : Janvier 2005
    Messages : 711
    Points : 751
    Points
    751
    Par défaut
    je t'ai donné le detail de mon calcul dans mon post de 12h28.. ta solution est fausse car tu fonctionne comme si chaque boucle faisait n iteration... et meme comme ca ca serait faux car tu ne tiendrais pas compte de la boucle while !! un truc en n^4 ca pourrait etre :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
     
    for(i=0,i<n)
       for(j=0,i<n)
          for(k=0,i<n)
             for(l=0,i<n)
               (O(1))
             fin
          fin
       fin
    fin
    dans ton cas, tu n'as pas besoin d'appliquer de formule complexe, car les X se simplifient. en fait, l'idee c'est que si X est grand, les 2 premiere boucle vont faire peu de tour, et les 2 autres beaucoup, et le contraire si X est petit. donc quand certaine boucle deviennent plus importante, d'aure le devienne automatiquement mons, ca se compense. c'est pour a qu'on a une complexité faible meme avec 4 boucles.

    conclusion : si, tu peux multiplier la complexité de chaque boucle, tu dois meme. mais elle ne sont jamais simultanement toute en O(n). donc ton resultat n'es pas faux, il est simplement un peu grossier, cad que tu prend "large".

  14. #14
    Membre éclairé
    Inscrit en
    Janvier 2005
    Messages
    711
    Détails du profil
    Informations forums :
    Inscription : Janvier 2005
    Messages : 711
    Points : 751
    Points
    751
    Par défaut
    et accessoirement, dans ton dernier calcul non plus, j'ai l'impression que tu ne tiens pas compte de la boucle while, donc tu devrais multiplie par log2(n)

  15. #15
    Membre du Club
    Profil pro
    Étudiant
    Inscrit en
    Septembre 2006
    Messages
    112
    Détails du profil
    Informations personnelles :
    Âge : 37
    Localisation : Belgique

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Septembre 2006
    Messages : 112
    Points : 58
    Points
    58
    Par défaut
    D'accord merci bien pour l'explication !

    Mais dans mon dernier calcul j'ai essayer en donnant des valeurs à n et j'ai tester ça me donne exactement (n² - 1)/3 itérations donc ça marche

    merci bien !

  16. #16
    Rédacteur

    Avatar de millie
    Profil pro
    Inscrit en
    Juin 2006
    Messages
    7 015
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2006
    Messages : 7 015
    Points : 9 818
    Points
    9 818
    Par défaut
    Pour moi, c'était autre chose :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
     int X = n;
     
         while (X > 1)
               for (int i = 0; i < n; i+= X)
                   for (int j = 0; j < n; j+= X)
                      for (int k = 0; k < X/2; k++)
                        for (int l = 0; l < X/2; l++)
     
               X = X/2;
    Dans le premier for, on fait : X/2 opération.
    Dans les deux for, on en fait donc : X²/4.

    Ensuite, les boucles i et j vont de X en X jusqu'à N, il y a donc n/X boucles.
    Donc pour i et j, il y a n²/X²

    Ce qui fait donc : n²/4 (sans le while)

    Avec le while, comme n²/4 ne dépend plus de X, c'est facile, il suffit de multiplier par log_2 n

    Soit une complexité en : n² log_2 n /4 en considérant que la représentation machine de n prend n bits.

    Avec la représentation classique de |n| = log_2 n, alors la complexité serait en : O(exp(n²) n)
    Je ne répondrai à aucune question technique en privé

  17. #17
    Membre éclairé
    Inscrit en
    Janvier 2005
    Messages
    711
    Détails du profil
    Informations forums :
    Inscription : Janvier 2005
    Messages : 711
    Points : 751
    Points
    751
    Par défaut
    ben c'est ce que j'avais dit dans mon premier post :-)

    la je crois qu'il parlait d'un autre exemple..

  18. #18
    Rédacteur

    Avatar de millie
    Profil pro
    Inscrit en
    Juin 2006
    Messages
    7 015
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2006
    Messages : 7 015
    Points : 9 818
    Points
    9 818
    Par défaut
    Citation Envoyé par jobherzt
    ben c'est ce que j'avais dit dans mon premier post :-)

    la je crois qu'il parlait d'un autre exemple..

    oui, j'ai vu ça après J'ai sauté le message et les autres avaient l'air de partir d'importe comment, donc j'avais voulu rectifier le tir

    Je n'avais vu que ton deuxième post ou tu as du faire une erreur de frappe :

    log2(n) * n^2 *(n^2)/4
    Je ne répondrai à aucune question technique en privé

  19. #19
    Membre du Club
    Profil pro
    Étudiant
    Inscrit en
    Septembre 2006
    Messages
    112
    Détails du profil
    Informations personnelles :
    Âge : 37
    Localisation : Belgique

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Septembre 2006
    Messages : 112
    Points : 58
    Points
    58
    Par défaut
    Oups, oui je parlais d'un autre bout de code

    Merci tout de même d'avoir refait le calcul

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Complexité de l'algorithme de multiplication matricielle de strassen
    Par judge06 dans le forum Algorithmes et structures de données
    Réponses: 3
    Dernier message: 09/07/2007, 08h27
  2. Complexité de l'algorithme de multiplication de Karatsuba
    Par judge06 dans le forum Algorithmes et structures de données
    Réponses: 4
    Dernier message: 27/03/2007, 13h02
  3. Complexité de l'algorithme de Tri Fusion
    Par judge06 dans le forum Algorithmes et structures de données
    Réponses: 10
    Dernier message: 26/03/2007, 23h04
  4. complexité d'un algorithme par un...algorithme??
    Par afrikha dans le forum Algorithmes et structures de données
    Réponses: 5
    Dernier message: 02/11/2005, 01h59
  5. [Fractale] Triangle de Sierpinski
    Par Florian.L dans le forum Algorithmes et structures de données
    Réponses: 6
    Dernier message: 19/01/2005, 00h20

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