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
    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

    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



    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 :

    [latex]\sum_{i=1}^{\mathcal{O}(\log n)} \mathcal{O}(i)[/latex]

    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
    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

    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
    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

    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
    N'y a-t-il pas [latex]\sum_{i=0}^{\log_2(n)} 2 {\lfloor}\frac{n}{2^i}{\rfloor}-1[/latex] itérations en tout ? Ce qui est égal à [latex]4n - log_2(n) - 3[/latex] si on ne prend pas la partie entière, ce qui correspond à une complexité de [latex]\mathcal{O}(n)[/latex].

    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.
    [latex]4 \times 16 - log_2(16) - 3 = 57[/latex]

  9. #9
    Candidat au Club
    merci bcq
    Citation Envoyé par mcc39 Voir le message
    N'y a-t-il pas [latex]\sum_{i=0}^{\log_2(n)} 2 {\lfloor}\frac{n}{2^i}{\rfloor}-1[/latex] itérations en tout ? Ce qui est égal à [latex]4n - log_2(n) - 3[/latex] si on ne prend pas la partie entière, ce qui correspond à une complexité de [latex]\mathcal{O}(n)[/latex].

    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.
    [latex]4 \times 16 - log_2(16) - 3 = 57[/latex]