Chapitre 1 : Complexité algorithmique - PDF

Chapitre1 : Complexité algorithmique  Supports de cours vol.1 – Période 2005-2014 17 Complexité algorithmique Comme on l’a vu lors de l’implémentation des types abstraits, il est souvent possible d’implémenter plusieurs solutions à un problèm...

Chapitre1 : Complexité algorithmique  Supports de cours vol.1 – Période 2005-2014 17 Complexité algorithmique Comme on l’a vu lors de l’implémentation des types abstraits, il est souvent possible d’implémenter plusieurs solutions à un problème donné. La question se pose alors de savoir quel algorithme est le plus efficace. Et pour effectuer cette comparaison, il est nécessaire de déterminer sur quels critères elle doit être effectuée. Le but de cette section est d’introduire le champ de la théorie de la complexité, dont l’un des buts est de répondre à ce type de question. 17.1 Introduction à la complexité 17.1.1 Motivation et principe Théorie de la complexité : théorie développée dans le but de comparer efficacement différents algorithmes entre eux, Afin de savoir lequel était le meilleur pour un problème donné. Jusqu’aux années 70, on caractérisait les algorithmes de manière empirique, en considérant :  Le temps d’exécution ;  L’espace mémoire utilisé ;  Les conditions d’exécution : o Taille des données o Type d’ordinateur o Système d’exploitation o Langage de programmation o Etc. exemple : Pour le problème consistant à calculer 1234 , sur un P4 à 3 GHz, avec un OS Windows XP et une implémentation en langage C, supposons que l’algorithme 𝐴 met 1,2 secondes et utilise 13 Mo de mémoire, alors que l’algorithme 𝐵 met 1,3 secondes et utilise 0,8 Mo. Alors on peut dire que 𝐴 est plus rapide que 𝐵, mais que 𝐵 est moins gourmand en mémoire. Le problème de cette démarche est qu’elle ne permet pas de comparer les algorithmes de manière objective, car ils ne sont pas les seuls facteurs intervenant dans la performance de résolution du problème : d’autres facteurs extérieurs interviennent également (matériel, logiciel...). La solution retenue est de se détacher de ses facteurs extérieurs, et donc de l’implémentation de l’algorithme. Pour cela, nous allons utiliser une approche plus théorique, reposant sur deux notions : les opérations élémentaires et les positions mémoire. Opération élémentaire : opération atomique, correspondant à une instruction assembleur. Rappelons qu’une instruction assembleur est atomique, dans le sens où elle correspond à un code directement interprétable par le processeur. Autrement dit, une instruction assembleur est associée à une action que le processeur peut réaliser, comme par exemple placer une certaine valeur dans à une certaine adresse en mémoire. Par comparaison, une instruction du langage C se décompose généralement en plusieurs instructions assembleur. La notion d’opération élémentaire va être utilisée pour représenter la consommation que l’algorithme analysé effectue en termes de temps de calcul. On dira par exemple qu’il a besoin d’effectuer 𝑥 opérations élémentaires pour résoudre le problème traité. Position mémoire : unité de mémoire élémentaire, correspondant généralement à un octet. La notion de position mémoire est une abstraction de l’occupation qu’un algorithme a de la mémoire. Elle va nous permettre d’évaluer cette consommation de façon indépendante de 178/232  Supports de cours vol.1 – Période 2005-2014 certaines conditions d’exécution mentionnées précédemment, en considérant le nombre de positions mémoires qu’il utilise. Ces deux notions nous permettent d’exprimer la complexité d’un algorithme en fonction de la taille des données qu’il traite. Taille des données d’un problème : entier(s) représentant la grandeur des paramètres reçus par l’algorithme devant résoudre le problème. Notez bien que la taille peut n’être représentée par un seul entier, mais aussi par plusieurs entiers distincts. Leur nombre et leur signification exacte dépendent fortement de la nature du problème étudié :  Nombre d’éléments à traiter ;  Grandeur des éléments à traiter ;  etc. exemples :  Tri d’un tableau de taille 𝑁 : la taille des donnés est 𝑁, le nombre d’éléments du tableau.  Calcul de 𝐶𝑛𝑝 : la taille des données est le couple 𝑛, 𝑝. L’idée est que si la taille est petite, le problème sera vraisemblablement plus facile à résoudre que si elle est énorme. On veut généralement savoir comment la complexité de l’algorithme évolue quand on fait grandir la taille du problème. Complexité d’un algorithme : nombre d’opérations élémentaires ou de positions mémoire dont l’algorithme a besoin pour résoudre un problème d’une certaine taille. Formellement, l’expression d’une complexité prend la forme d’une fonction mathématique de la taille des données. exemples :  Si le tri du tableau a une complexité 𝑓 𝑁 = 𝑎𝑛 + 𝑏, on dira que le tri possède une complexité linéaire.  Si un autre algorithme de tri possède une complexité 𝑓 𝑁 = 𝑛2 , alors on considèrera que ce tri a une complexité quadratique.  La complexité du second tri est supérieure à celle du premier. 17.1.2 Complexités spatiale et temporelle On distingue deux types de complexités : temporelle et spatiale. Complexité temporelle : nombre total d’opérations élémentaires pour exécuter l’algorithme. La complexité temporelle correspond donc au décompte de toutes les opérations élémentaires que l’algorithme a besoin d’effectuer pour résoudre le problème. Complexité spatiale : nombre maximal de positions mémoire utilisées au cours de l’exécution. À la différence des opérations élémentaire, qui s’enchaîne de façon séquentielle, l’occupation mémoire est une quantité qui évolue au cours du temps : en fonction de l’état de la pile (appels de fonction) et du segment de données (allocation dynamique) l’algorithme peut augmenter et diminuer le nombre de positions mémoire qu’il utilise. La complexité spatiale correspond à l’occupation maximale atteinte par l’algorithme au cours de son exécution. Attention donc à ne pas considérer le total de toutes les positions mémoires occupées au cours de l’exécution, ou bien juste l’occupation mémoire observée juste avant que l’algorithme se termine. 179/232  Supports de cours vol.1 – Période 2005-2014 exemple : 2 fonctions différentes calculant le produit des nombres d’un tableau d’entiers. int produit1(int tab[N]) 1 { int i; 2 int resultat=1; 3 for(i=0;i 0, ∃𝑥0 > 0 𝑓 croît plus vite (ou aussi vite) que 𝑔 𝑓∈Ω 𝑔 ∀𝑥 ≥ 𝑥0 : 𝑓 𝑥 ≥ 𝑎 × 𝑔 𝑥 (𝑔 est une borne inférieure asymptotique de 𝑓) 𝑓 et 𝑔 croissent à la même vitesse 𝑓∈Θ 𝑔 𝑓 ∈ 𝑂 𝑔 ⋀𝑓 ∈ Ω 𝑔 (𝑔 est une borne approchée asymptotique de 𝑓) exemples : soient les fonctions 𝑓 𝑥 = 3𝑥 2 + 1, 𝑔1 𝑥 = 4𝑥, 𝑔2 𝑥 = 𝑥 2 + 4, 𝑔3 𝑥 = 3 𝑥. On a alors :  𝑓 ∈ 𝑂 𝑔2 : prenons 𝑎 = 3 et 𝑥0 = 1. o 𝑓 𝑥 = 3 × 12 + 1 = 4. o 3 × 𝑔2 𝑥 = 3 12 + 4 = 7.  𝑓 ∈ 𝑂 𝑔3 : prenons 𝑎 = 1 et 𝑥0 = 4 : o 𝑓 𝑥 = 3 × 42 + 1 = 49. 183/232  Supports de cours vol.1 – Période 2005-2014 o 𝑔3 𝑥 = 43 = 64.  𝑓∈Ω 𝑔1 : prenons 𝑎 = 1 et 𝑥0 = 1 : o 𝑓 𝑥 = 3 × 12 + 1 = 4. o 𝑔1 𝑥 = 4 × 1 = 4.  𝑓∈Ω 𝑔2 : prenons 𝑎 = 1 et 𝑥0 = 2 : o 𝑓 𝑥 = 3 × 22 + 1 = 13. o 𝑔2 𝑥 = 22 + 4 = 8.  𝑓∈Θ 𝑔2 car 𝑓 ∈ Ω 𝑔2 et 𝑓 ∈ 𝑂 𝑔2. Dans ce cours, on utilisera essentiellement la notation en grand 𝑂, qui permet de majorer le comportement d’une fonction. Bien sûr, on veut obtenir la borne supérieure de degré le plus petit possible. La notation en Θ sera également utilisée, plus rarement, quand il est possible de borner la complexité de l’algorithme de manière plus précise. On distingue habituellement différentes familles d’algorithmes en fonction de leur borne supérieure :  Complexité constante : 𝑂 1.  Complexité logarithmique : 𝑂 log 𝑥.  Complexité log-linéaire : 𝑂 𝑥 log 𝑥.  Complexité linéaire : 𝑂 𝑛.  Complexité quadratique : 𝑂 𝑥 2 , cubique 𝑂 𝑛3 , ou plus généralement : polynômiale 𝑂 𝑥 𝑘.  Complexité exponentielle 𝑂 𝑘 𝑥. Remarque : en informatique, quand la base d’un logarithme n’est pas précisée, c’est qu’il s’agit d’un logarithme de base 2. Pour simplifier le calcul de complexité, on utilise les abus de notation suivants :  𝑓 ∈ 𝑂 𝑔 sera noté 𝑓 = 𝑂 𝑔  Dans une formule, 𝑂 𝑔 représente une fonction anonyme appartenant à 𝑂 𝑔  𝑂 𝑥 0 sera noté 𝑂 1 exemple : Dans 2𝑥 2 + 3𝑥 + 1 = 2𝑥 2 + 𝑂 𝑥 , 𝑂 𝑥 représente toute fonction 𝑓 appartenant à 𝑂 𝑥 tout en vérifiant l’égalité. Ici, il s’agit de 𝑓 𝑥 = 3𝑥 + 1. Les propriétés suivantes seront utilisées lors des calculs de complexité :  Soit 𝑝 𝑥 un polynôme de degré 𝑑, alors on a : 𝑝 𝑥 = Θ 𝑥 𝑑  𝑂 𝑓 + 𝑂 𝑔 = 𝑂 𝑓 + 𝑔 = 𝑂(max 𝑓 + 𝑔 ) (distributivité pour l’addition)  𝑂 𝑓 𝑂 𝑔 = 𝑂 𝑓𝑔 (distributivité pour le produit)  ∀𝑎, 𝑏 > 0: 𝑂 log 𝑎 𝑛 = 𝑂 log 𝑏 𝑛 En pratique, pour obtenir la borne asymptotique supérieure une fois qu’on a exprimé 𝑓 sous la forme d’un polynôme, il suffit de ne conserver que le terme de degré le plus élevé, et d’ignorer les coefficients constants. exemple : 2𝑥 2 + 3𝑥 + 1 = 𝑂 2𝑥 2 + 𝑂 3𝑥 + 𝑂 1 = 𝑂 2𝑥 2 = 𝑂 𝑥 2 17.1.6 Complexité asymptotique L’intérêt de la notation asymptotique est double. D’une part, les calculs de complexité sont simplifiés. D’autre part, l’information utile est préservée (on obtient l’ordre de grandeur). 184/232  Supports de cours vol.1 – Période 2005-2014 exemple : on calcule les complexités asymptotiques des fonctions produit1 et produit2 dans le pire des cas. Toutes les opérations élémentaires ont une complexité asymptotique constante : 𝑂 1.  Complexités temporelles : o Première fonction : 𝑇1 𝑁 = 𝑂( 5𝑁 + 4 𝑐) = 𝑂 5𝑁𝑐 = 𝑂 𝑁 o Seconde fonction : 𝑇2 𝑁 = 𝑂( 7𝑁 + 6 𝑐) = 𝑂 7𝑁𝑐 = 𝑂 𝑁 Si on compare les complexités temporelles dans le pire des cas, les deux fonctions ont la même complexité asymptotique. Pourtant, on sait (d’après nos calculs précédents) que les deux fonctions n’ont pas la même complexité dans le pire des cas : 𝑇1 𝑁 = 4 + 5𝑁 et 𝑇2 𝑁 = 6 + 7𝑁. Le fait que les deux fonctions aient la même complexité asymptotique signifie que lorsque 𝑁 tend vers l’infini, la différence entre 𝑇1 et 𝑇2 est négligeable. produit1 produit2 Remarque : quand on compare des algorithmes en termes de complexité asymptotique, il ne faut pas perdre de vue le fait que cette comparaison n’est valable que quand on parle de données de grande taille. En effet, sur de petites données, un algorithme en 𝑂 𝑁 2 peut être plus rapide qu’un algorithme en 𝑂 𝑁. exemple : considérons les algorithmes 𝐴 et 𝐵 suivants :  L’algorithme 𝐴 possède une complexité temporelle de 𝑇𝐴 𝑁 = 100𝑁.  L’algorithme 𝐵 possède une complexité temporelle de 𝑇𝐵 𝑁 = 2𝑁 2. 𝑵 Algorithme 𝑨 Algorithme 𝑩 10 1000 200 100 10000 20000 1000 100000 2000000 10000 1000000 200000000 algo.A algo.B Pour des valeurs de 𝑁 inférieures à 50, on peut observer que 𝐵 est plus rapide que 𝐴. Au- dessus de 50, 𝐴 est largement plus performant, et la différence ne cesse de s’accroître. 185/232  Supports de cours vol.1 – Période 2005-2014 Asymptotiquement, la complexité de 𝐴 (qui est en 𝑂 𝑁 ) est plus faible que celle de 𝐵 (qui est en 𝑂 𝑁 2 ). L’ordre de grandeur de la complexité d’un algorithme est un concept indépendant des contraintes matérielles (machine, langage, implémentation…). Par conséquent, l’utilisation d’une machine plus puissante ne change rien en termes de comparaison asymptotique. exemple : supposons qu’une opération élémentaire est effectuée en 1 unité de temps. Soit un problème traité par l’algorithme 𝐴 en 5000 opérations élémentaires, c'est-à-dire en autant d’unités de temps. Ce problème a une taille 𝑁 = 50. Pour l’algorithme 𝐵, un problème traitable en 5000 opérations élémentaires correspond également à un problème de taille 𝑁 = 50. Supposons qu’on dispose d’une machine 10 fois plus puissante : elle effectue 10 opérations élémentaires en 1 seule unité de temps. Alors pour la même durée, l’algorithme 𝐴 peut traiter un problème de taille 𝑁 = 500, c'est-à-dire 10 fois plus gros qu’avec la machine moins puissante. L’algorithme 𝐵 peut traiter un problème de taille 𝑁 = √5000⁄2 ≈ 158, c'est-à-dire seulement 3 fois plus gros qu’avec la machine moins puissante. 17.2 Calcul de complexité Dans cette sous-section, nous nous intéressons plus concrètement au calcul de complexité pour des algorithmes itératifs, en considérant séparément les complexités temporelle et spatiale. 17.2.1 Complexité temporelle Pour réaliser un calcul de complexité temporelle, on associe une certaine complexité à chaque élément composant l’algorithme. Nous nous concentrons ici sur la complexité dans le pire des cas.  Opération élémentaire (on considère une instruction) : temps constant 𝑂 1.  Appel d’une fonction : soit 𝑓 la complexité au pire de la fonction ; alors la complexité de l’appel est en 𝑂 𝑓.  Instruction de test (if ou switch) : soient 𝑓 la complexité de la condition, et 𝑔𝑖 les complexités des différents blocs (then, else, case…) ; alors la complexité au pire est en 𝑂 (𝑓 + max 𝑔𝑖 ). 𝑖  Instruction de répétition (for, do, while) : soient 𝑓 la complexité du bloc et de la condition, et 𝑔 la borne supérieure du nombre d’itérations au pire, alors la complexité au pire est en 𝑂 𝑓 ∙ 𝑔  Séquence d’instructions : soit 𝑓𝑖 la complexité de la ième instruction ; alors la complexité au pire de la séquence est en 𝑂 ∑𝑖 𝑓𝑖. exemple : recherche du plus petit élément dans un tableau non trié de taille 𝑁. int cherche_minimum (int tab[N]) { int i; 1 int indice=0; 𝑂 1 2 for(i=1;i