Quelle est la complexité de l'algorithme ?
Qu'est-ce que la complexité algorithmique ? La complexité algorithmique est un concept très important qui permet de comparer les algorithmes afin de trouver celui qui est le plus efficace.
Il existe une notation standard qui s'appelle big O et qui permet de mesurer la performance d'un algorithme.Qu'est-ce qu'un algorithme complexe ?
La complexité d'un algorithme est une mesure du temps[1] requis par l'algorithme pour accomplir sa tâche, en fonction de la taille[2] de l'échantillon à traiter.
On dira d'un problème qu'il est aussi complexe que le meilleur algorithme connu pour le résoudre.Comment mesurer la complexité d'un algorithme ?
On mesure alors la complexité en temps d'un algorithme comme le nombre de ces opérations élémentaires.
Par exemple, en considérant élémentaire l'addition de 2 chiffres, poser l'addition de deux nombres de n chiffres nous fera effectuer n additions à 1 chiffre, la complexité sera donc de n.24 mai 2019- Réponse algorithmique
Pour mesurer le temps d'exécution d'un algorithme, on définit la complexité en temps qui représente le nombre d'étapes qui sont nécessaires pour résoudre le problème pour une entrée de taille donnée.
ANALYSE DALGORITHMES
MEC6405-Analyse Expérimentale des contraintes
Module Contraintes & Déformations
Méthodologie danalyse des contraintes résiduelles par diffraction
Analyse des contraintes résiduelles par diffraction des rayons X
Cours de résistance des matériaux
Resistance des materiaux de base
Cours 1ère année ENTPE Résistance des matériaux – Partie 1
RDM_BIpdf
Falquet, CUI, Université de Genève1 de 14Algorithmes et complexitéCombien de temps mon algorithme mettra-t-il pour résoudre un problème donné ?Combien d'espace mémoire faut-il prévoir ?Problème et instanceProblème général : tester si un nombre est premierProblème particulier (instance) : tester si 494059397730 est premierUne instance est caractérisée par sa tailleIl y a différentes manières de définir la taillep.ex. taille(494059397730) = 494059397730 (linéaire)ou taille(494059397730) = 12 chiffres (logarithmique)G.
Falquet, CUI, Université de Genève2 de 14ComplexitéPour résoudre une instance de taille n fixée.
Complexité d'un algorithme en temps= nombre d'instructions exécutées (ordre de grandeur) = fonction de nen supposant que les instructions prennent un temps constantComplexité en espace = nombre de cellules mémoire utilisées (ordre de grandeur) = fonction de nG.
Falquet, CUI, Université de Genève3 de 14Exemple: résolution d'une équationTrouver x tels que ax + b = 0 (a différent de 0)Avec a et b inférieurs à MAX{x ¬ Ð b / a}Nombre d'opérations arithmétiques effectuées : 2 Complexité en temps : constanteT(n) = kTemps effectif : dépend de la machineG.
Falquet, CUI, Université de Genève4 de 14Exemple pn1.r ¬ 1;2.s ¬ 0;3.tant que (s ¹ n) {// nombre d'itérations = n4.r ¬ r * p;5.s ¬ s + 1;}G.
Falquet, CUI, Université de Genève5 de 14Nombre d'opérations exécutées1.r ¬ 1;1 fois2.s ¬ 0;1 fois3.tant que (s ¹ n) {n + 1 fois 4.r ¬ r * p;n fois5.s ¬ s + 1;n foisen tout : 2 + (n+1) + 2n opérations= 3 + 3n opérationsSi n est grand 3n >> 3T(n) = environ k * 3n Le temps croît linéairement en fonction de n, indépendament de p.
G.Falquet, CUI, Université de Genève6 de 14Exemple pn bien amélioréObservation :p2n = (pn)2p2n+1 = (pn)2 . p1p26 = (p13)21 multiplicationoù p13 = (p6)2 . p2 multiplicationsoù p6 = (p3)21 multiplicationoù p3 = (p)2 . p2 multiplicationsEN TOUT6 multiplications (à la place de 25)Nombre d'étapes : log2(n)À chaque étape 1 ou 2 multiplications ==> T(n) £ 2 . log2(n)G.
Falquet, CUI, Université de Genève7 de 14Algorithme (récursif)On définit une fonction récursivefonction puissance(p, n) {si ( n = 0 ) retourne 1sinon {y ¬ puissance(p, n/2)y ¬ y * ysi ( n mod 2 = 1) y ¬ y * pretourne y}}Complexité : T(n) proportionnel à 2log2(n)Amélioration pour n = 10243x1024 / 2log2(1024) = 3072 / 20 = 153.6 fois plus rapideG.
Falquet, CUI, Université de Genève8 de 14Cas de complexitéÀ cause des instructions si et tant queUn algorithme ne suite pas toujours le même chemin pour résoudre un problème.=> Pour deux problèmes de taille n il peut exécuter des nombres différents d'opérations.=> La complexité n'est pas constante pour un problème de taille nExemple intuitif Pour un "processeur" humain, il est plus facile de trier la liste(2, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)que la liste(34, 1, 101, 3, 8, 221, 14, 71, 6, 106, 93, 2, 88)G.
Falquet, CUI, Université de Genève9 de 14Définition des cas de complexitéPour un algorithme donné et un problème de taille n on distingueLe meilleur des casles données qui font que la complexité est minimaleÐ pour certains algo de tri: liste déjà dans l'ordreÐ résoudre une équation dont tous les coefficients sont nulsLe pire des casnombre maximum d'opération que peut faire l'algorithme - pour certains algo de tri: liste dans l'ordre inverse ou liste déjà triéeLe cas moyen le nombre moyen d'opérations calculé sur tous les problèmes de taille ndifficile à définirG.
Falquet, CUI, Université de Genève10 de 14Impact pratiqueMesurer si les ressources dont on dispose sont suffisante pour résoudre les problèmes auxquels on veut s'attaquer; Calculer la taille maximum des problèmes qu'on peut attaquer étant donné les ressources dont on dispose.AlgorithmeComplexitéen tempsTaille maximum du problème que l'on peut résoudre en 1 seconde1 minute1 heureA1n1'000'00060'000'0003'600'000'000A2n log(n)627462'801'420133'378'000A3n21000774560'000A4n31003911'532A52n192531G.
Falquet, CUI, Université de Genève11 de 14Impact sur l'interface utilisateurLe temps de calcul peut changer radicalement l'usage de la machineEx. vérifier l'orthographe d'un motsi T < 0.1 sec : vérification possible "en direct" pendant qu'on tape le textesi T > 0.1 sec : la vérification devient une opération à effectuer séparémentEx. calcul d'une image en 3Dsi T < 0.1 sec : animation (jeu vidéo)si T < 1 sec : travail interactif sur une image (création d'images 3D, dessin)si T plus grand : calcul différé (films d'animation réalistes calculés avec des "fermes de processeurs")G.
Falquet, CUI, Université de Genève12 de 14Ordres de grandeurDifficile de calculer exactement le nombre d'instructions qui seront exécutéesOn s'intéresse à l'ordre de grandeur de ce nombre en fonction de n.
Notation O( f )g(x) Î O( f ) s'il existe un n0 et un c tels que g(x) £ c f(x) dès que n ³ n0. But : utiliser des fonctions f simples telles que 1, n, n2, n3, É, nk, 2n , log(n).G.Falquet, CUI, Université de Genève13 de 14Graphiquementn0g(x) = 1.2x2 + cos(x4) - log(x+1) + 3x2g Î O (x2)G.
Falquet, CUI, Université de Genève14 de 14Quelques ordres de grandeurconstante k Î O(1)linéaireax + b Î O(x) quadratiqueax2 + bx + c Î O(x2)Épolynômial akxk + akÐ1xkÐ1 + É + a1x + a0 Î O(xk) xq Î O(2x)polynome < exponentielle]"p2x Ï O(xp)exponentielle toujours > polynômelog(n) Î O(n)logarithme < linéaire"aax Ï O(log(n))linéaire toujours > logarithme