Complexité des Algorithmes - PDF

Complexité Définition L\'**analyse de la complexité d\'un algorithme** consiste en l\'étude formelle de la quantité de ressources (par exemple de [[temps]](https://fr.wikipedia.org/wiki/Complexit%C3%A9_en_temps) ou d\'[[espace]](https://fr.wikipedia.org/wiki/Complexit%C3%A9_en_espace)) nécessaire...

Complexité Définition L\'**analyse de la complexité d\'un algorithme** consiste en l\'étude formelle de la quantité de ressources (par exemple de [[temps]](https://fr.wikipedia.org/wiki/Complexit%C3%A9_en_temps) ou d\'[[espace]](https://fr.wikipedia.org/wiki/Complexit%C3%A9_en_espace)) nécessaire à l\'exécution de cet [[algorithme]](https://fr.wikipedia.org/wiki/Algorithme).  On a 3 cas : Une image contenant texte, Police, capture d'écran, ligne Description générée automatiquement -On s intéresse a la 3 -ème cas car si l ordinateur peut compiler la 3 eme cas donc évidement il peut compiler les autres cas [Pourquoi on calcule la complexité ?] Pour un problème donnée , si on a plusieurs solution pour choisir le meilleur on devons comparer et analyser les performances de chaque algorithmes les types de complexité   Les règles de calcule de complexité **1:** Pour les opérations de base la complexité égale o(1)\ **2:** pour les boucles : la compexcitee = complexitee de boucles inten \* nombre de fois que le boucle intern est repetee [exemple:]  3: Pour si /sinon: La complexité = max ( complexité de si, complexité de sinon ) [Exemple:] Une image contenant texte, Police, ligne, capture d'écran Description générée automatiquement La complexité egal o(2n) Remarques: -Les constantes multiplicatives égal 1 ( o(5n)=o(n) ) -Les constantes additives est nul ( o(n+1)=o(n)) -Le termes le plus élevé est conservée (o(n²+2\^n)=o(2\^n)) Un exemple pour chaque types : O(1):  O(n): Une image contenant texte, logiciel, Logiciel multimédia, Icône d'ordinateur Description générée automatiquement O(n²):  O(log n): Une image contenant texte, capture d'écran, Police, nombre Description générée automatiquement O(2\^n):