Complexité d'un algorithme
Répondre à la discussion
Affichage des résultats 1 à 1 sur 1

Complexité d'un algorithme



  1. #1
    e5mm100

    Complexité d'un algorithme


    ------

    Bonjour le prof nous a donné une correction sur un exercice de complexité algorithmique mais je n'ai pas tout compris. Pouvez -vous m'aider ?
    Voici l'exercice :

    DEBUT :
    -i <-- 1
    - TQ i <= n FAIRE :
    ----j <-- 2
    ----TQ j<= (n^0.5) FAIRE :
    --------J <-- j+1
    -----FTQ
    -----i<-- 1
    -FTQ
    FIN

    Correction :
    Boucle intérieur :
    - La boucle ne dépend que de la variable j
    - j est initialisé a 2 avant la boucle
    -Elle est modifiés a l'instruction 7 (j<-- j+1)
    - Les valeurs prisent par j sont donc celles de la suite : j0= 2; jr+1= jr +1 autrement dit jr=2+r
    - La condition d’arrêt de la boucle est satisfaite quand j>(n^0.5)
    c'est à dire 2+r > (n^0.5) autrement dit r=(n^0.5)-1 // J'ai pas compris comment on est passé de 2+r>(n^0.5) à r=(n^0.5)-1
    - Toute les opérations de la boucle sont en Θ(1) on en déduit donc que : // J'ai pas compris pourquoi elles sont en Θ(1), comment on le sait ?
    c(n)= Θ(1) *((n^0.5)-1)=Θ((n^0.5)-1)=Θ((n^0.5)) // Ici je n'ai absolument rien compris au calcule

    Boucle principal :
    - La boucle ne dépend que de la variable i
    - j est initialisé a 1 avant la boucle
    -Elle est modifiés a l'instruction 9 (i<-- i+1)
    - La condition d’arrêt de la boucle est satisfaite quand i=n+1
    - La complexité de la boucle principal est Θ(1)+Θ(n^0.5)= Θ(n^0.5) // Ici idem que en haut j'ai pas compris le calcule

    Pour la complexité total = Θ(n*(n^0.5)) // Il faut additionner les complexité des 2 boucles ?


    Je vous remercie pour votre aide !!

    -----
    Dernière modification par e5mm100 ; 10/06/2020 à 15h31.

Discussions similaires

  1. Complexité en espace d'un algorithme résursif
    Par kizakoo dans le forum Programmation et langages, Algorithmique
    Réponses: 1
    Dernier message: 02/01/2020, 19h41
  2. complexité d'un algorithme recursif
    Par bmce dans le forum Programmation et langages, Algorithmique
    Réponses: 5
    Dernier message: 08/12/2016, 07h25
  3. preuve et complexite algorithme
    Par tlop dans le forum Programmation et langages, Algorithmique
    Réponses: 0
    Dernier message: 27/10/2016, 00h41
  4. Complexité de l'algorithme de Shor
    Par invite06fcc10b dans le forum Discussions scientifiques
    Réponses: 14
    Dernier message: 19/11/2009, 19h26
  5. Complexité d'algorithme
    Par invite84c98a4b dans le forum Mathématiques du supérieur
    Réponses: 6
    Dernier message: 23/12/2006, 23h00