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é algorithmique d'un bout de code


Sujet :

Algorithmes et structures de données

  1. #1
    Candidat au Club
    Femme Profil pro
    Étudiant
    Inscrit en
    décembre 2011
    Messages
    4
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : Tunisie

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2011
    Messages : 4
    Points : 3
    Points
    3
    Par défaut Complexité algorithmique d'un bout de code
    je voudrais vérifier si la complexité du bout de code suivant est nlogn ?

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    i=n
    s=0
    tq (i>0) faire
       j = 2 * i 
       tq (j>1) faire
          s=s+(j-i)*(s+1)
          j = j-1 
       ftq 
      i = i div 2
    ftq

  2. #2
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    2 712
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 2 712
    Points : 5 927
    Points
    5 927
    Par défaut
    La question est plus ou moins : combien de fois on passe par la ligne n°6 de ce programme.

    Si n est grand (disons 10 Millions), on va passer par cette ligne combien de fois ?
    +20 Millions de fois quand i vaut 10 Millions
    +10 Millions de fois quand i vaut 5 Millions
    +5 Millions de fois quand i vaut 2.5 Millions
    Etc. En tout, on passe 40 Millions de fois par cette ligne n°6.

    Et quand n vaut 10 Milliards, On va multiplier tous ces nombres par 1000... donc non, la complexité n'est pas en n*log(n).
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  3. #3
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    août 2008
    Messages
    24 991
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2008
    Messages : 24 991
    Points : 176 985
    Points
    176 985
    Par défaut


    Quelques questions pour t'aider à trouver la réponse :
    - combien de fois la boucle intérieure (sur j) est-elle exécutée, en fonction de i et de n ?
    - combien de fois la boucle extérieure (sur i) est-elle exécutée, uniquement en fonction de i ?
    - combien vaut la somme ?

    Ma solution :

    La boucle extérieure est exécutée O(log n) fois, la boucle intérieure O(i) fois, la complexité totale est donc :

    Formule mathématique

    C'est plus du O(log^2 n), en calculant la somme partielle.
    Vous souhaitez participer aux rubriques Qt ou PyQt (tutoriels, FAQ, traductions), HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  4. #4
    Candidat au Club
    Femme Profil pro
    Étudiant
    Inscrit en
    décembre 2011
    Messages
    4
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : Tunisie

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2011
    Messages : 4
    Points : 3
    Points
    3
    Par défaut
    la boucle a l’intérieur est exécutée 2n(1+1/2+1/2^2+1/2^3+1/2^4+...........+1/2^logn)

    donc a quoi est égale cette somme ?

  5. #5
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    2 712
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 2 712
    Points : 5 927
    Points
    5 927
    Par défaut
    la boucle a l’intérieur est exécutée 2n(1+1/2+1/2^2+1/2^3+1/2^4+...........+1/2^logn) : oui

    a quoi est égale cette somme ?
    : relis la discussion. Sachant qu'on a simplement besoin d'une estimation plus ou moins précise.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  6. #6
    Candidat au Club
    Femme Profil pro
    Étudiant
    Inscrit en
    décembre 2011
    Messages
    4
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : Tunisie

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2011
    Messages : 4
    Points : 3
    Points
    3
    Par défaut
    donc la complexité sera inférieure a n*log n et je crois qu'elle doit être aussi supérieure a log^2n ?

    quelle est la solution ?

    je crois que ça sera log(logn)*n

  7. #7
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    2 712
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 2 712
    Points : 5 927
    Points
    5 927
    Par défaut
    N+ N/2 + N/4 + N/8 ... etc , ça vaut 2N
    Ici, la somme commence par 2N + N + N/2 +N/4 ... donc ça donne 4N.
    Si on veut être pécis, ça donne 4N-1 ; mais pour un calcul de complexité, c'est 4N. Surtout qu'il y a un autre petit truc qui fait des différences, c'est qu'on divise par 2 à chaque étape, et on arrondit à l'entier inférieur si la division par 2 ne tombe pas juste. Et notre calcul ne tient pas compte de cet arrondi.

    A mon avis, pas de log() dans le résultat, même si effectivement, dans les étapes intermédiaires, il y a du log().
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  8. #8
    Membre régulier
    Homme Profil pro
    Développeur C++
    Inscrit en
    avril 2011
    Messages
    46
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 29
    Localisation : France, Doubs (Franche Comté)

    Informations professionnelles :
    Activité : Développeur C++
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : avril 2011
    Messages : 46
    Points : 83
    Points
    83
    Par défaut
    N'y a-t-il pas Formule mathématique itérations en tout ? Ce qui est égal à Formule mathématique si on ne prend pas la partie entière, ce qui correspond à une complexité de Formule mathématique.

    Par exemple, si on part avec n=16, la boucle principale itérera 5 fois:
    • i=16 -> j=32 -> +31 itérations
    • i=8 -> j=16 -> +15 itérations
    • i=4 -> j=8 -> +7 itérations
    • i=2 -> j=4 -> +3 itérations
    • i=1 -> j=2 -> +1 itération


    Au total, il y a 31+15+7+3+1=57 itérations.
    Formule mathématique

  9. #9
    Candidat au Club
    Femme Profil pro
    Étudiant
    Inscrit en
    décembre 2011
    Messages
    4
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : Tunisie

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2011
    Messages : 4
    Points : 3
    Points
    3
    Par défaut merci bcq
    Citation Envoyé par mcc39 Voir le message
    N'y a-t-il pas Formule mathématique itérations en tout ? Ce qui est égal à Formule mathématique si on ne prend pas la partie entière, ce qui correspond à une complexité de Formule mathématique.

    Par exemple, si on part avec n=16, la boucle principale itérera 5 fois:
    • i=16 -> j=32 -> +31 itérations
    • i=8 -> j=16 -> +15 itérations
    • i=4 -> j=8 -> +7 itérations
    • i=2 -> j=4 -> +3 itérations
    • i=1 -> j=2 -> +1 itération


    Au total, il y a 31+15+7+3+1=57 itérations.
    Formule mathématique

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

Discussions similaires

  1. la sauvegarde des bouts de code ?
    Par blackhorus dans le forum Autres éditeurs
    Réponses: 2
    Dernier message: 02/10/2005, 14h34
  2. [XML][XSL] déplacer bout de code XML
    Par majanissa dans le forum XSL/XSLT/XPATH
    Réponses: 8
    Dernier message: 14/09/2005, 18h17
  3. Besoin d'explications sur un bout de code
    Par zizitop dans le forum C
    Réponses: 7
    Dernier message: 26/04/2005, 15h51
  4. bout de code à dechifrer svp
    Par bball dans le forum C
    Réponses: 32
    Dernier message: 21/01/2005, 00h23

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