Remerciez-le!

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

2021-2022 Cours Informatique Complexité d’un algorithme I Généralités La questi

2021-2022 Cours Informatique Complexité d’un algorithme I Généralités La question de la performance est centrale en informatique. Si un problème est traité en un temps raisonnable, l’utilisateur est satisfait. On s’attache en général peu à une mesure précise du temps d’exécution, mais uniquement à une approximation de ce temps. Si le temps obtenu est perçu comme relativement long, se posera la question d’une solution plus eﬃcace. La machine étant ﬁxée, l’amélioration portera alors sur la façon dont sont conçus les algorithmes en fonction du volume n de données à traiter. Par exemple, si en doublant le volume de données, un algorithme renvoie un résultat en multipliant le temps d’exécution par 2 et un autre le renvoie en multipliant le temps d’exécution par n > 2, on optera évidemment pour le premier : on dit que sa complexité temporelle est meilleure. Ajoutons que l’on peut aussi déﬁnir sa complexité spatiale aﬁn de prendre en compte l’espace mémoire occupé au cours de l’exécution d’un algorithme. Plus sa complexité est grande, plus le programme mettant en oeuvre l’algorithme aura besoin de zones mémoires pour stocker les données. I.1 Complexité temporelle et spatiale d’un algorithme Déﬁnition : La complexité 1 temporelle d’un algorithme est une information 2 sur son temps d’exécution liée au volume n de données à traiter. La complexité temporelle d’un programme est la complexité temporelle de l’algorithme associé. Remarques : • La complexité temporelle ne dépend pas : — des performances du processeur de la machine sur laquelle le programme est exécuté, — des modes d’accès à la mémoire vive et des modes de stockage, — du langage de programmation dans lequel l’algorithme est traduit, — du compilateur/interpréteur exécuté. On se place sur une machine idéalisée dont la mémoire est considérée comme inﬁnie et l’accès aux données se fait en temps constant. • Le volume de données (on dit aussi la taille des données) dépend du problème étudié : — il peut s’agir du nombre d’éléments constituant les paramètres de l’algorithme (par exemple le nombre d’éléments d’un tableau), — dans le cas d’algorithmes de nature arithmétique (le calcul de n! par exemple), il peut s’agir d’un entier passé en argument, — dans le cas d’algorithmes avec des chaînes de caractères, il peut s’agir de la longueur des chaînes de caractères. Noter que le volume de données est un entier naturel caractérisant le nombre de données et non son occupation mémoire en octets (ou en bits). Déﬁnition : La complexité spatiale d’un algorithme est une estimation de l’espace mémoire occupé au cours de l’exécution d’un programme en fonction du volume n de données à traiter. La complexité spatiale d’un programme est la complexité spatiale de l’algorithme associé. Le programme de CPGE met l’accent sur la complexité temporelle et c’est cette notion que nous allons développer. 1. On dit aussi le « coût ». 2. Ce n’est pas le temps d’exécution réel sur une machine donnée, avec des logiciels donnés et des processus en cours d’exécution. Lycée Michelet - classes de PCSI 1 2021-2022 Cours Informatique I.2 Mesure de la complexité temporelle La mesure de la complexité temporelle nécessite un modèle. Dans celui-ci : — on précise les opérations élémentaires qui, par hypothèse, se déroulent en temps borné par une constante, — on suppose que la complexité temporelle d’un algorithme est proportionnelle au nombre d’opérations élémentaires. Sans être exhaustif, les opérations génériques suivantes sont considérées comme élémentaires : — les opérations arithmétiques (+,-,*,/,//,%), — la comparaison de données : relation d’égalité (==), d’ordre (<,>,...), — le transfert de données : lecture (input, open, readline,...) et écriture dans un empla- cement mémoire (print, close, writeline,...), — les instructions de contrôle (if,elif,else, while,for), — l’aﬀectation en général (sans tenir compte de la complexité liée à l’exécution de l’expression à droite de celle-ci), càd. a = ; par exemple a = 0. Remarques : Les hypothèses ci-dessus sont acceptées, mais simpliﬁcatrices. En eﬀet, elles dé- pendent partiellement du langage de programmation. Par exemple, — Les entiers python sont de type long (i.e. 8 octets) (à partir de la version 3.0) : les opérations arithmétiques ne sont donc pas toujours élémentaires. On supposera cependant leur temps d’exécution borné. — La comparaison entre chaînes de caractères n’est pas élémentaire. Seule la comparaison entre deux caractères sera supposée élémentaire. — La recopie d’un tableau entier n’est pas élémentaire. Seule la copie d’un élément d’un tableau sera supposée élémentaire. Par ailleurs, il existe des opérations liées à des structures de données, appelées des types dans Python. Certaines opérations se déroulent en temps constant (ou en temps amorti constant 3) et on peut les considérer comme des opérations élémentaires : — l’ajout dans un tableau t de type list, càd. t.append(item) ou t[i] = item — l’ajout dans un dictionnaire d via d[i]=item — l’accès à un élément via son index dans un itérable (tableau t de type list, dictionnaire d, chaîne de caractères s,...) càd. t[i], d[i], s[i], ... — l’accès à la longueur d’un itérable (tableau t de type list, dictionnaire d, chaîne de caractères s,...) càd. len(t), len(d), len(s),... — la suppression d’un élément dans un dictionnaire càd. del dict[key] (alors que ce n’est pas en temps constant pour un tableau de type list) — la récupération des clés d’un dictionnaire càd. dict.keys() — le test d’existence d’un élément dans un dictionnaire (type dict) ou un ensemble (type set) via e in s (ou e not in s). Attention ! Ce test d’existence avec les tableaux de type list n’est absolument pas une opération élémentaire. Parmi les opérations non élémentaires, on peut citer sans être exhaustif : la recherche d’un élément dans un tableau de type list, la suppression d’un élément dans un tableau de type list, les tests d’égalité entre listes (t1 == t2), le slicing de listes (t[a:b]). 3. Cela signiﬁe que le temps est constant dans la grande majorité des cas, mais qu’il peut y avoir des exceptions. Lycée Michelet - classes de PCSI 2 2021-2022 Cours Informatique I.3 La notation O Notation de Landau : on dit qu’une suite numérique (un) est dominée par la suite (vn), et on note un = O(vn), quand il existe n0 ∈N et un réel k > 0 tel que : ∀n ≥n0, |un| ≤k|vn| Exemple : Considérons le programme de détermination du nombre d’occurrences dans un tableau de type list. On veut déterminer la complexité de la fonction nbre_occurrences. 2 def nbre_occurrences (x:object , t:list) -> int: 3 c = 0 4 for i in range(len(t)): 5 if t[i] == x: 6 c = c + 1 7 return c Complexité : • L’aﬀectation c = 0 compte pour une opération élémentaire (on dit qu’elle est en O(1), car majorée par une constante). • La boucle bornée for i in range(len(t)) se déroule len(t) fois, où len(t) est une opération élémentaire. • L’instruction de contrôle if, l’accès à t[i], ainsi que le test d’égalité t[i] == x se déroulent en temps constant (3 opérations). • Le calcul de l’expression c+1 ainsi que l’aﬀectation c = c+1 se déroulent en temps constant (2 opérations). • return c est une opération élémentaire. Conclusion : Si n = len(t) (taille de l’entrée), le traitement se réalise en un maximum de 5n + 2 opérations élémentaires. Or, 5n + 2 ≤6n, donc que la complexité temporelle dans le pire des cas de la fonction nbre_occurrences est O(n). On dit aussi que la complexité temporelle est linéaire. Une fois le travail d’analyse détaillée ci-dessus fait, on se rend compte que l’on aurait pu le simpliﬁer comme suit grâce à la notation de Landau : La longueur du tableau n = len(t) est une mesure de la taille du problème considéré. • L’aﬀectation c = 0 se déroule en O(1). • La boucle bornée for i in range(len(t)) se déroule n fois. De plus, len(t) se déroule en O(1). — Les instructions if t[i] == x et c = c + 1 se déroulent en O(1). Donc dans le pire des cas, la boucle for et son bloc de code se déroulent en O(n). • return c se déroule en O(1). Conclusion : par somme, la complexité temporelle dans le pire des cas de la fonction nbre_occurrences est en O(n). I.4 Le pire et le meilleur des cas. Reprenons la fonction nbre_occurrences. — Dans le meilleur des cas, t[0] == x : la boucle s’arrête après 1 passage. On dit que la complexité temporelle dans le meilleur des cas est en O(1). — Dans le pire des cas, x n’est pas dans t : la boucle s’arrête après n passage(s). On dit que la complexité temporelle dans le pire des cas est en O(n). Par défaut, on déterminera la complexité temporelle dans le pire des cas. Lycée Michelet - classes de PCSI 3 2021-2022 Cours Informatique I.5 Classes de complexité asymptotique Déﬁnition : La complexité asymptotique est le comportement de la complexité d’un algorithme lorsque la taille de son entrée est asymptotiquement grande. Il peut s’agir a priori de complexité asymptotique moyenne ou uploads/Science et Technologie/ complexite-d-x27-un-programme.pdf