Répondre à la discussion
Affichage des résultats 1 à 7 sur 7

Complexité d'algorithme



  1. #1
    natachaSt

    Complexité d'algorithme


    ------

    Bonjour,
    y a t il kelkun qui pouré me dire la compléxité d'un tel algithme, et la methode kil utilise pour la trouver :


    pour i allant de 1 a n par pas de 1 faire
    pour j allant de i à 2*i par pas de 1 faire
    p:=0
    finpour
    finpour

    merci

    -----

  2. Publicité
  3. #2
    Nicolas666666

    Re : Complexité d'algorithme

    peux tu expliquer plus ton message? le language sms est interdit au fait et en plus on ne comprend pas ce que tu dis

  4. #3
    natachaSt

    Re : Complexité d'algorithme

    alors voila, je voudrais savoir le temps d'execution aproximatif d'un tel algorithme...
    merci

  5. #4
    azt

    Re : Complexité d'algorithme

    Bonsoir,
    ton programme ne veut pas dire grand chose, il doit être incomplet.
    Dans quel sens parles-tu de complexité ?

    Cordialement,
    AZT
    Nous sommes toujours de la taille de l'univers que nous découvrons. [Frédérick Tristan]

  6. A voir en vidéo sur Futura
  7. #5
    Taar

    Re : Complexité d'algorithme

    Salut !
    On suppose qu'à chaque passage le programme effectue un nombre fini d'opérations, minoré par un entier k et majoré par un entier K.

    Ici par exemple :
    une opération pour initialiser i
    une opération pour incrémenter i
    une opération de test de i
    une opération pour initialiser j
    une opération pour incrémenter j
    une opération de test de j
    une opération de mise de p à 0
    plus une dizaine d'opérations pour faire les sauts nécessaires
    Disons k=1 et K=20, grossièrement.

    Toutes les opérations citées ne sont pas effectuées à chaque passage (par exemple, l'incrémentation de i n'a lieu que quand on sort de la boucle sur j), mais ça n'a pas d'importance puisqu'on veut un majorant et un minorant.

    Comme on effectue 2+3+4+...+(n+1)=(n+1)(n+2)/2-1 passages, on peut estimer que le nombre d'opérations effectuées N est compris entre an=(n+1)(n+2)/2-1 et
    bn=20((n+1)(n+2)/2-1).

    Maintenant, mathématiquement on a (n+1)(n+2)/2-1 ~ n2/2 lorsque n tend vers l'infini.
    Donc N est compris entre deux nombres qui sont respectivement équivalents à n2/2 et 10n2. C'est donc un algorithme en n2.

    Oublions le minorant. N est majoré par bn ~ 10n2. Donc N=O(n2). C'est donc un algorithme en O(n2).

    En termes de complexité, tout dépend de la taille d des données :

    Si tes données, c'est juste n, alors la taille des données est d ~ log2(n) (puisqu'un entier n est représenté par environ log2(n) bits), donc l'algorithme est en O((exp2(d))2)=O(exp2(2d)), il est exponentiel.

    Si tes données sont de taille n où à peu près (c'est à dire d ~ C.n où C est une constante), ce qui est le cas par exemple si tu as un tableau à n entrées, alors l'algorithme est en O(d2), il est polynomial.

    Le lien entre le nombre d'opérations N et le temps T nécessaire pour les effectuer est supposé être un lien de la forme N ~ D.T où D est une constante (c'est-à-dire que N et T sont (à peu près) proportionnels). Donc tout ce qui a été dit sur N se répète pour T.
    Dernière modification par Taar ; 22/12/2006 à 00h51.

  8. #6
    natachaSt

    Re : Complexité d'algorithme

    Bonjour,

    merci bien Taar pour cette explication bien argumenté...

    cordialement

  9. Publicité
  10. #7
    natachaSt

    Re : Complexité d'algorithme

    merci, mais j'arrive pas à l'appliqué a d'autres algorithmes. pas resemple :

    i:=n;
    tantque i>0 faire
    si i mod 2 =1 alors
    i:=i-1
    sinon
    i:=i/2
    finsi
    fin tantque

    (et j'en ai d'autres encor, alors je n'arretré mé message que un efois ke j'auré comment ca marche )

Discussions similaires

  1. Pb D'algorithme
    Par lecureuildu80 dans le forum Logiciel - Software - Open Source
    Réponses: 6
    Dernier message: 17/10/2007, 12h15
  2. En parlant de complexité...
    Par The Nameless dans le forum Epistémologie et Logique (archives)
    Réponses: 4
    Dernier message: 28/08/2007, 17h37
  3. complexité algorithmique
    Par benoir126 dans le forum Mathématiques du supérieur
    Réponses: 4
    Dernier message: 18/03/2007, 10h31
  4. Question de complexité
    Par PopolAuQuébec dans le forum Discussions scientifiques
    Réponses: 148
    Dernier message: 15/12/2006, 15h29
  5. Complexité
    Par isozv dans le forum Mathématiques du supérieur
    Réponses: 26
    Dernier message: 10/12/2004, 19h58