Scribd Logo
Importer

Bienvenue sur Scribd !

  • 333 vues

    Complexité

    Transféré par

    elkamondo
    Ce document présente les notions de base de la complexité algorithmique. Il définit la complexité en temps et en espace d'un algorithme et explique comment évaluer la complexité asymptotique d'un algorithme, notamment pour les boucles, les algorithmes récursifs et les principales classes de complexité.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd

    Complexité

    Transféré par

    elkamondo
    333 vues25 pages
    Ce document présente les notions de base de la complexité algorithmique. Il définit la complexité en temps et en espace d'un algorithme et explique comment évaluer la complexité asymptotique d'un algorithme, notamment pour les boucles, les algorithmes récursifs et les principales classes de complexité.

    Description originale:

    Complexité

    Copyright

    © © All Rights Reserved

    Formats disponibles

    PDF, TXT ou lisez en ligne sur Scribd

    Avez-vous trouvé ce document utile ?

    Ce contenu est-il inapproprié ?

    Ce document présente les notions de base de la complexité algorithmique. Il définit la complexité en temps et en espace d'un algorithme et explique comment évaluer la complexité asymptotique d'un algorithme, notamment pour les boucles, les algorithmes récursifs et les principales classes de complexité.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    333 vues25 pages

    Complexité

    Transféré par

    elkamondo
    Ce document présente les notions de base de la complexité algorithmique. Il définit la complexité en temps et en espace d'un algorithme et explique comment évaluer la complexité asymptotique d'un algorithme, notamment pour les boucles, les algorithmes récursifs et les principales classes de complexité.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    sur 25

    Algorithmique...

    Complexit
    Luc Brun
    luc.brun@greyc.ensicaen.fr

    A partir de travaux de
    Habib Abdulrab(Insa de Rouen)

    Complexite p.1/25

    Plan...
    Notion de complexit
    Comment valuer la complexit dun algorithme
    Exemple de calculs de complexit

    Complexite p.2/25

    Notion de complexit (1)


    Comment valuer les performances dun algorithme
    diffrents algorithmes ont des cots diffrents en termes de
    temps dexcution (nombre doprations effectues par lalgorithme),
    taille mmoire (taille ncessaire pour stocker les diffrentes structures de
    donnes pour lexcution).
    Ces deux concepts sont appel la complexit en temps et en espace de
    lalgorithme.

    Complexite p.3/25

    Notion de complexit (2)


    La complexit algorithmique permet de mesurer les performances dun
    algorithme et de le comparer avec dautres algorithmes ralisant les mme
    fonctionnalits.
    La complexit algorithmique est un concept fondamental pour tout
    informaticien, elle permet de dterminer si un algorithme a et meilleur
    quun algorithme b et sil est optimal ou sil ne doit pas tre utilis. . .

    Complexite p.4/25

    Temps dexcution (1)


    Le temps dexcution dun programme dpend :
    1. du nombre de donnes,
    2. de la taille du code,
    3. du type dordinateur utilis (processeur,mmoire),
    4. de la complexit en temps de lalgorithme abstrait sous-jacent.

    Complexite p.5/25

    Temps dexcution (2)


    Soit n la taille des donnes du problme et T (n) le temps dexcution de
    lalgorithme. On distingue :
    Le temps du plus mauvais cas Tmax (n):
    Correspond au temps maximum pris par lalgorithme pour un problme de
    taille n.
    Le temps moyen Tmoy :
    Temps moyen dexcution sur des donnes de taille n ( suppositions sur
    la distribution des donnes).
    Tmoy (n) =

    r
    X

    pi Tsi (n)

    i=1

    pi probabilit que linstruction si soit excute,


    Tsi (n) : temps requis pour lexcution de si .
    Complexite p.6/25

    Temps dexcution
    Rgles gnrales :
    1. le temps dexcution (t.e.) dune affectation ou dun test est considr
    comme constant c,
    2. Le temps dune squence dinstructions est la somme des t.e. des
    instructions qui la composent,
    3. le temps dun branchement conditionnel est gal au t.e. du test plus le max
    des deux t.e. correspondant aux deux alternatives (dans le cas dun temps
    max).
    4. Le temps dune boucle est gal la somme du cot du test + du corps de la
    boucle + test de sortie de boucle.

    Complexite p.7/25

    Problmes du temps dexcution (1)


    Soit lalgorithme suivant :
    Nom: Calcul dune somme de carrs
    Role: Calculer la valeur moyenne dun tableau
    Entre: n : entier
    Sortie: somme : rel
    Dclaration: i: Naturel
    dbut
    somme 0.0
    pour i 0 n-1 faire
    somme somme+i*i
    finpour
    fin
    Complexite p.8/25

    Problmes du temps dexcution (2)


    Tmoy (n) = Tmax (n) = c1 + c1 +
    n(c2 + c3 + c4 + c5 + c1 )
    P
    5
    = 2c1 + n
    i=1 ci

    avec c1 : affectation, c2 : incrmentation, c3 test, c4 addition, c5 multiplication.


    Trop prcis

    1. Faux,

    2. Inutilisable.
    Notion de complexit : comportement asymptotique du t.e.:
    Tmax (n) = Tmoy (n) nC

    Complexite p.9/25

    Estimation asymptotique
    Dfinition 1 Une fonction f est de lordre de g , crit avec la notation Grand-O
    comme: f = O(g) , sil existe une constante c et un entier n0 tels que:
    f (n) cg(n), pour tout n n0
    selon la dfinition ci-dessus, on aura:
    f1 (n) = 2n + 3 = O(n3 ), 2n + 3 = O(n2 ), 2n + 3 = O(n)au plus juste
    f2 (n) = 7n2
    = O(2n ), 7n2
    = O(n2 ) au plus juste

    mais, 7n2 NEST PAS O(n)

    Complexite p.10/25

    galit de complexit
    Dfinition 2 2 fonctions f et g sont dgale complexit, ce qui scrit comme:
    O( f )= O( g ) (ou f = (g)), ssi f = O(g) et g = O(f )
    exemples:
    n, 2n , et 0, 1n sont dgale complexit: O(n) = O(2n) = O(0, 1n)
    O(n2 ) et O(0, 1n2 + n) sont dgale complexit: O(n2 ) = O(0, 1n2 + n)

    par contre: 2n et n3 se sont PAS dgale complexit: O(2n) 6= O(n3 )


    Dfinition 3 une fonction f est de de plus petite complexit que g, ce qui scrit
    comme: O(f ) < O(g) , ssi f = O(g) mais g 6= O(f )
    exemples:
    100n est de plus petite complexit que 0, 01n2 : O(100n)< O(0, 01n2 ),
    log2 n est de plus petite complexit que n: O(log2 n) < O(n),

    par contre: 0, 1n2 nest PAS de plus petite complexit que 10n2 : O(0, 1n2 )
    = O(10n2 )
    Complexite p.11/25

    Proprits
    Rflexivit:
    g = O(g)

    Transitivit :
    si f = O(g) et g = O(h) alors f = O(h)
    Produit par un scalaire :O(f ) = O(f ), > 0.
    Somme et produit de fonctions :
    O(f )+O(g)=O(max{f, g})
    O(f ).O(g)=O(f.g)

    Complexite p.12/25

    Complexit dune boucle


    pour i 1 n faire
    s
    finpour
    avec s=O(1).
    Temps de calcul de s: Ts = C
    Nombre dappels de s : n
    Temps de calcul total : T (n) = nTs = O(n)
    Complexit : O(n)

    Complexite p.13/25

    Boucles imbriques
    Thorme 1 La complexit de p boucles imbriques de 1 n ne contenant que
    des instructions lmentaires est en O(np ).
    Preuve:

    vrai pour p = 1,
    supposons la ppt vrai lordre p. Soit :
    pour i 1 n faire
    instruction
    finpour
    o instruction contient p boucles imbriques.
    Soit Tinst (n) le temps dexcution de instruction et T (n) le temps total.
    T (n) = nTinst (n) avec Tinst (n) Cnp pour n n0 (par hypothse).
    T (n) Cnp+1 T (n) = O(np+1 )
    

    Complexite p.14/25

    Boucles tant que


    h1
    tant que h n faire
    h 2*h
    fintantque
    Test, multiplication, affectation : O(1) : T = C
    Nombre ditrations : log2 (n).
    Temps de calcul : T (n) = C log2 (n) = O(log2 (n))

    Complexite p.15/25

    Complexit dun algorithme rcursif (1)


    Soit lalgorithme :
    fonction factorielle (n: Naturel) : Naturel
    dbut
    si n = 0 alors
    retourner 1
    sinon
    retourner n*factorielle(n-1)
    finsi
    fin

    Complexite p.16/25

    Complexit dun algorithme rcursif (2)


    c1 test, c2 multiplication.

    T(0)=c1
    T(n)=c1 +c2 +T(n-1)
    T (n) = nc2 + (n + 1)c1

    Soit C = 2max{c1 , c2 }
    T (n) Cn + c1 = O(n)

    Complexit en O(n).
    Les calculs de complexit dalgorithmes rcursifs induisent naturellement des
    suites.

    Complexite p.17/25

    Algorithmes rcursifs en O(log2(n)) (1)


    Thorme 2 Soient, debut, f in et n = f in debut trois entiers. La complexit
    de lalgorithme ci dessous est en O(log2 (n)).
    procdure f (debut,fin)
    Dclaration Entiermilieu
    dbut
    in
    milieu debut+f
    2
    si fin-milieu > 1 et milieu-debut > 1 alors
    s
    sinon
    si test alors
    f (debut,milieu)
    sinon
    f (milieu,fin)
    finsi
    finsi
    fin
    Complexite p.18/25

    Algorithmes rcursifs en O(log2(n)) (2)


    Tests, s : O(1)
    T (n) = T ( n2 ) + C
    T ( n2 ) = T ( n4 ) + C
    ..
    ..
    .
    = .
    T (1) = T (0) + C
    T (n) = T (0) + Clog2 (n)

    Complexite p.19/25

    Algorithmes rcursifs en O(n log2(n)) (1)


    procdure f (debut,fin)
    Dclaration Entier milieu
    dbut
    in
    milieu debut+f
    2
    si fin-milieu > 1 et milieu-debut > 1 alors
    s1
    sinon
    pour i 1 n faire
    s2
    finpour
    f(dbut,milieu)
    f(milieu,fin)
    finsi
    fin
    Complexite p.20/25

    Algorithmes rcursifs en O(n log2(n)) (2)


    Tests, s : O(1)
    Boucle : O(n).
    T (n)
    2T ( n2 )
    ..
    .

    = n + 2T ( n2 )
    = n + 4T ( n4 )
    ..
    = .

    2p1 T (2) = n + 2p T (1)


    T (n)
    = n p + 2p T (1)

    avec p = [log2 (n)].


    On a de plus:
    O(n log2 (n) + nT (1)) = O(n log2 (n))

    Complexite p.21/25

    Principales complexits
    O(1) : temps constant,
    O(log(n)) : complexit logarithmique (Classe L),
    O(n) : complexit linaire (Classe P),
    O(n log(n))
    O(n2 ),O(n3 ),O(np ) : quadratique, cubique,polynomiale (Classe P),
    O(pn ) complexit exponentielle (Classe EXPTIME).
    O(n!) complexit factorielle.

    Complexite p.22/25

    Influence de la complexit
    n 2n.
    O(1) O(log2 (n)) O(n) O(n log2 (n)) O(n2 ) O(n3 ) O(2n )
    t
    t+1
    2t
    2t + 2n
    4t
    8t
    t2

    n = 102
    n = 103
    n = 104
    n = 105
    n = 106

    1
    1s
    1s
    1s
    1s
    1s

    log2 (n)
    6s
    10s
    13s
    17s
    20s

    n
    0.1ms
    1ms
    10ms
    0.1s
    1s

    n log2 (n)
    0.6ms
    10ms
    0.1s
    1.6s
    19.9s

    n2
    10ms
    1s
    100s
    2.7h
    11, 5j

    n3
    1s
    16.6min
    11, 5j
    32a
    32 103 a

    2n
    4 1016 a

    Complexite p.23/25

    Limites de la complexit
    La complexit est un rsultat asymptotique : un algorithme en O(Cn2 ) peut
    tre plus efficace quun algorithme en O(C n) pour de petites valeurs de n
    si C C ,
    Les traitements ne sont pas toujours linaires Il ne faut pas supposer
    dordres de grandeur entre les diffrentes constantes.

    Complexite p.24/25

    Conseils
    Qualits dun algorithme :
    1. Maintenable (facile comprendre, coder, dboguer),
    2. Rapide
    Conseils :
    1. Privilgier le point 2 sur le point 1 uniquement si on gagne en complexit.
    2. ce que fait lalgorithme doit se lire lors dune lecture rapide : Une ide
    par ligne. Indenter le programme.
    3. Faire galement attention la prcision, la stabilit et la scurit.
    La rapidit dun algorithme est un lment dun tout dfinissant les qualits de
    celui-ci.
    Complexite p.25/25

    Vous aimerez peut-être aussi