Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

La complexité algorithmique 1 Introduction Nous terminons ce cours d’algorithmi

La complexité algorithmique 1 Introduction Nous terminons ce cours d’algorithmique et de structures de données par une notion très importante et que l’on ne cessera de rencontrer désormais : la complexité algorithmique. En effet, nous avons appris à développer des programmes (et des modules sous forme de fonctions et de procédures), et au delà du plaisir que nous prenons parfois à le faire, nous nous apercevons que les solutions que nous proposons sont parfois—voire souvent—différentes de celles proposées par les autres (nos amis, nos collègues, etc.). Ceci est normal : un problème donné peut avoir plusieurs solutions, et donc plusieurs algorithmes implémentant ces solutions. Cependant, nous nous interrogeons souvent quelle est la meilleure solution? Cette question invite une autre question : “meilleure en quoi?" En effet, deux algorithmes répondant au même besoin et renvoyant les mêmes résultats peuvent être différents en termes d’espace et/ou de temps. Et nous parlons, par conséquent, de (1) complexité en temps d’exécution, et de (2) complexité en espace (mémoire, ou même disque, ou autres ressources) nécessaire pour que l’algorithme fonctionne. Pour simpliﬁer, nous considérons dans ce cours la complexité en temps d’exécution. En d’autres termes : à quel point un algorithme est-il rapide? Et nous tâcherons donc de formaliser cette comparaison d’efﬁcacité par une notation simple. 2 Exemple d’introduction Supposons que l’on vous demande de stocker une séquence d’entiers dont le nombre est inconnu avant l’exécution du programme. Vous optez pour une liste linéaire chainée. Vous pensez donc à insérer des éléments dans une LLC. Nous avons au moins deux façons de le faire 1. La première étant d’insérer chaque nouvel élément à la tête de la liste, la deuxième consisterait à l’insérer à la ﬁn de la liste. Comparez ces deux solutions. Il est évident que la première est plus rapide que la deuxième, n’est ce pas? La première alloue de l’espace pour l’élément, y met l’entier en question, et fait en sorte qu’il soit la nouvelle tête de la LLC. 1. sans compter les solutions bizarres 1 La deuxième, en revanche, après avoir alloué l’espace et y avoir mis la valeur, parcoure la liste jusqu’à la ﬁn pour y insérer l’élément nouvellement créé. Mais ce n’est pas tout. Remarquez que le temps pris par le premier algorithme est constant et ne dépend nullement de la taille de la liste, alors que le second algorithme prendrait plus de temps (à parcourir la liste) à mesure que la liste devienne plus longue. Nous comprenons donc qu’il ne sufﬁt souvent pas que l’algorithme fonctionne, il est parfois aussi important qu’il soit efﬁcace. 3 La notation de Landau L’exemple précédent nous a donné une idée de la différence qu’il peut y avoir entre deux algorithmes censés faire la même chose. Mais comment traduit-on cette différence de façon formelle ou mathématique? 3.1 Intuitivement Avant de le faire, commençons par une explication intuitive. Lorsque nous insérons un élément à la tête d’une liste, le temps d’exécution de dépend pas de la taille de la liste. Alors que lorsque nous l’insérons à la queue, plus il y a d’éléments dans la liste plus le programme prendra de temps pour le faire, et ce de façon linéaire. Lorsqu’un programme nécessite un temps d’exécution constant et indépen- dant de la taille des données (n) à traiter, nous dison que sa complexité est constante, et est égale à O(1), et c’est prononcé comme suit : Big-O de 1. La différence en temps d’exécution quand n est incrémenté est de 0. Lorsqu’un algorithme nécessite n fois plus de temps qu’il prendrait pour le faire lorsqu’il n’y a qu’une seule donnée, nous disons que sa complexité est linéaire et nous la notons par O(n). Si n est incrémenté de 1, le nombre d’éléments à parcourir est lui aussi incrémenté de 1. Maintenant supposons que l’on vous demande de chercher le maximum d’une matrice carrée n × n. L’on devrait alors parcourir chaque ligne de cette matrice, et pour chacune de ces lignes parcourir chaque colonne aussi. Nous devons effectuer n × n vériﬁcations pour connaitre ce maximum. Nous disons dans ce cas que cet algorithme est d’une complexité quadratique et c’est noté par O(n2). Si n est incrémenté de 1, nous aurons (n + 1)2 de cases à traiter, et pas seulement n + 1. Un dernier exemple : Supposons que nous recherchons une valeur donnée x dans un arbre binaire de recherche (BST) qui a n nœuds. Remarquez qu’à chaque itération nous éliminons une branche de l’arbre de façon récursive. Au pire donc nous prendrons log(n) itérations et la complexité est notée justement par O(log(n)). 2 3.2 Formellement Pour plus de détails quant à l’aspect mathématique de la notation de Landau, revoir le cours d’analyse mathéma- tique. Supposons que le temps d’exécution d’un algorithme donné soit déﬁni par une fonction T(n) où n est le nombre de données. Nous disons que : T(n) est 2 O(f(n)) si et seulement s’il existe deux constantes c ∈R et n0 ∈N pour lesquelles T(n) ≤cf(n) et ce pour tout n ≥n0. La fonction f(n) est une borne supérieure pour T(n). Dit simplement, si l’on comparait le taux de croissance de T(n) nous dirons qu’ils est inférieur à celui de f(n). 3.3 Comportement asymptotique Le but de cette analyse est de comprendre le comportement dit asymptotique de l’algorithme. C’est à dire, de connaitre son efﬁcacité lorsque n est très grand. Si un algorithme donné est d’une complexité égale à O(f(n)), alors on s’attend à ce que son temps d’exécution ne croisse pas plus que f(n). 3.4 Quelques caractéristiques du Big-O Vous pouvez démontrer ces ca- ractéristiques en cherchant les bonnes valeurs des constantes c. La somme : Soient T1 et T2 les temps d’exécution de deux parties consécu- tives P1 et P2 d’un programme donné. Si T1(n) est O(f(n)) et T2(n) est O(g(n)), alors T1(n) + T2(n) est O(max(f(n), g(n))). En d’autres termes : O(f(n)) + g(n)) = O(max(f(n), g(n))). Multiplication par une constante (O(kf(n))) = O(f(n)). Produit (O(f(n) × g(n))) = O(f(n)) × O(g(n)). 3.5 Autres notations En plus du Big-O, il existe d’autres notation existent et qui décrivent d’autres bornes, notamment : Big-Omega : T(n) est Ω(f(n)) si et seulement s’il existe c ∈R et n0 ∈N tels que T(n) ≥f(n) pour tout n ≥n0. Theta : T(n) est Θ(f(n)) si T(n) est O(f(n)) et T(n) est Ω(f(n)). Little-o : T(n) est o(f(n)) si T(n) est O(f(n)) et T(n) n’est pas Θ(f(n)). 4 Quelques complexités usuelles Dans l’analyse des programmes, nous retrouvons souvent ces quelques com- plexités classées de la plus faible à la plus forte. O(log(n)) : Logarithmique O(n) : Linéaire O(n2) : Quadratique O(nk) : Polynomiale O(nn), O(ak), O(n!) : Exponentielle 2. Ou que T(n) ∈O(f(n)) 3 5 Règles de calcul Pour calculer la complexité d’un algorithme, nous avons quelques règles simples : 1. Toute opération élémentaire est d’une complexité constante O(1), car son temps d’exécution est constant et ne dépend pas de la taille des données. 2. La complexité d’une séquence de deux blocs d’instructions P1 et P2 est égale à la complexité du plus grand d’entre eux. (Revoir la somme ci- dessus) 3. La complexité d’une conditionnelle (si/sinon) est égale à la complexité du bloc le plus complexe. C’est un peu comme si l’on envisageait le cas où le bloc ayant la plus grande complexité serait exécuté. 4. La complexité d’une boucle est égale à la somme des complexités de toutes les itération du bloc. Si, par exemple, nous avons une boucle “pour" ne contenant que des instruction élémentaires, sa complexité serait égale à la somme, et si cette boucle itère sur les données, elle serait donc de O(n). 5.1 Quelques exemples Nous présentons ci-après quelques exemples d’illustration. En les analysant, et en essayant d’appliquer les règles ci-dessus, vous arriverez à calculer la complexité d’autres algorithmes par vous-mêmes. Rehcrehce dans un tableau La recherche d’un élément dans un tableau non trié est d’une complexité égale à O(n), car nous devons itérer n fois au pire pour trouver (ou pas) la valeur recherchée, et le nombre d’itérations croitra avec le nombre d’éléments dans le tableau. Recherche dans un tableau trié Si le tableau est trié : nous adoptons une recherche par dichotomie, donc nous enlevons n/2 à chaque fois. La complexité d’un tel algorithme est beau- coup plus faible que la précédente car elle est égale à O(log(n)). À titre d’exemple, prenez un tableau de 8 éléments. Nous nous positionnons au milieu, si la valeur recherchée est inférieure à celle du milieu, nous limitons notre recherche au premier 4 éléments du tableau (sinon aux 4 derniers). Nous refaisons cette opération avec ce sous-tableau de 4 éléments, et ainsi de suite. En d’autres termes, au bout d’au plus 3 itérations nous avons notre réponse. (8 = 23 donc 3 = log(8)) Produit matriciel Le produit de deux matrices A et B : Nous multiplions et additionnons les lignes de A par les colonnes de B. Nous avons trois boucles imbriquées et qui dépendent toutes les deux de la taille des données. La complexité est uploads/Religion/ bigo.pdf