Un probl`eme concretLaquelle de ces deux fonctions est la meilleure?IN 101 - Cours 041 int factoriel(int n) {2 int i, res;3 res = 1;30 septembre 20114 for (i=2; i 0, ∃n ∈N , ∀n ≥ n , 0 ≤ f(n) ≤ c ×g(n).0 04 for (i=1; i 0, ∃n ∈N, ∀n ≥ n , c ×g(n) ≤ f(n) ≤ c ×g(n).6 } 0 07 return sum;8 }Exemples : 2 2 2n +n+1=Θ n =Θ 2000n +1000000Pour une simple boucle for la complexit´e est facile `acalculer:log(n)=O(n)la taille ...
Qu’est-cequelacomplexite´? La notion centrale en algorithmique
Lacomplexite´d’unalgorithmemesuresonequeins`nirttie´cfficae: enfonctiondelatailledesdonne´esa`traiter, asymptotiquement, dans le pire cas, ou en moyenne.
Enpratique,pouruneentr´eedetaillen: on compte le nombre d’dsbeitnoe´arpoaseres,ssai´ecen onregardecommentcenombre´evolueasymptotiquement.
Pour une simple boucleforre:lcul`acacilestfaee´tixelpmocal latailledel’entr´eeestn la fonction faitnmultiplications etnadditions molpxetilcatsee´nileriae´leiltalatrenl’dee´.ene Unpeudere´flexionpermetdecalculercelaentempsconstant: n(n+1)(2n+1) sum of squares(n) = 6 2 additions, 3 multiplications, une division.
Notationsdecomplexite´ Comparaison asymptotique
De´finitions: Complexit´epolynomialesilaelbaosrte´vune k ∃k>0,f(n) =O(n). Complexit´eexponentielleelbasilaeeralirr´eng´en´ n ∃b>1,b=O(f(n)).
Complexite´doublement exponentielle n 2 par exemple :f(n.) = 2 Complexite´sous-exponentielle √ n par exemple :f(n) = 2 .
√ 2 log(n)nnnlog(n)n n 3n n2 n2exp(n)n!n2
Note : les valeurs propres de la matrice sontϕet 1−ϕ.
M´ethodesde programmation
Algorithme glouton
Unalgorithmegloutonestunalgorithmeite´ratifqui`achaque´etape essaye des’approcher au maximumde la solution.
Par exemple : lerendudemonnaie:quellesommedebillets/pie`cespermet d’atteindreunevaleurdonn´ee? Pour rendre 37 euros, on calcule 37 = 20 + 10 + 5 + 2. ets/billcesfpi`eseavldsseelrutesaleuqtnonoitulosoptimale. leproble`meduvoyageurdecommerce:quelestlepluscourt chemin passant parneenv´s?leilonsd Onvatoujoursa`lavillelaplusprochenonencorevisit´ee. donne une bonne solution, mais rarement optimale.
Quelquesautresme´thodes
Forcebrute:nomdonne´a`unalgorithmequitrouvelasolutionen essayant toutes les solutions possibles. recherche de clef en cryptographie.
Diviserpourre´gner:m´ethoder´ecursivequiconsiste`adiviser unproble`meensous-probl`emes,´ruoseerdroblus-pset`emelosse recombiner.tstaul´rselse algorithmes de tri (voir cours 05).
Algorithmesg´en´etiques:algorithmepourtrouverunesolution (quasi-)optimaled’unprobl`emed’optimisationenpartantdeso-lutionsapproch´ees,enlesfaisante´volueretenless´electionnant. un des projets d’IN104.
Par exemple : suitedoublementr´ecursive:enstockantlesvaleursinterm´ediaires defibo1on obtientfibo2. n passe deΘ()`2aΘ(nome´.erinu)elitintsapeunemud coefficients binomiaux avec le triangle de Pascal voir TD 04.