Computational complexityIn computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) and memory storage requirements. The complexity of a problem is the complexity of the best algorithms that allow solving the problem. The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory.
Complexité en tempsEn algorithmique, la complexité en temps est une mesure du temps utilisé par un algorithme, exprimé comme fonction de la taille de l'entrée. Le temps compte le nombre d'étapes de calcul avant d'arriver à un résultat. Habituellement, le temps correspondant à des entrées de taille n est le temps le plus long parmi les temps d’exécution des entrées de cette taille ; on parle de complexité dans le pire cas. Les études de complexité portent dans la majorité des cas sur le comportement asymptotique, lorsque la taille des entrées tend vers l'infini, et l'on utilise couramment les notations grand O de Landau.
Algorithme de triUn algorithme de tri est, en informatique ou en mathématiques, un algorithme qui permet d'organiser une collection d'objets selon une relation d'ordre déterminée. Les objets à trier sont des éléments d'un ensemble muni d'un ordre total. Il est par exemple fréquent de trier des entiers selon la relation d'ordre usuelle « est inférieur ou égal à ». Les algorithmes de tri sont utilisés dans de très nombreuses situations. Ils sont en particulier utiles à de nombreux algorithmes plus complexes dont certains algorithmes de recherche, comme la recherche dichotomique.
Tri à bullesvignette|Visualisation statique du tri : les étapes vont de gauche à droite. À chaque étape une permutation est faite. La couleur la plus foncée a le plus de valeur et trouve sa place définitive (en bas) en premier. Le tri à bulles ou tri par propagation est un algorithme de tri. Il consiste à comparer répétitivement les éléments consécutifs d'un tableau, et à les permuter lorsqu'ils sont mal triés. Il doit son nom au fait qu'il déplace rapidement les plus grands éléments en fin de tableau, comme des bulles d'air qui remonteraient rapidement à la surface d'un liquide.
Théorie de la complexité (informatique théorique)vignette|Quelques classes de complexité étudiées dans le domaine de la théorie de la complexité. Par exemple, P est la classe des problèmes décidés en temps polynomial par une machine de Turing déterministe. La théorie de la complexité est le domaine des mathématiques, et plus précisément de l'informatique théorique, qui étudie formellement le temps de calcul, l'espace mémoire (et plus marginalement la taille d'un circuit, le nombre de processeurs, l'énergie consommée ...) requis par un algorithme pour résoudre un problème algorithmique.
Tri par insertionEn informatique, le tri par insertion est un algorithme de tri classique. La plupart des personnes l'utilisent naturellement pour trier des cartes à jouer. En général, le tri par insertion est beaucoup plus lent que d'autres algorithmes comme le tri rapide (ou quicksort) et le tri fusion pour traiter de grandes séquences, car sa complexité asymptotique est quadratique. Le tri par insertion est cependant considéré comme l'algorithme le plus efficace sur des entrées de petite taille.
Classe de complexitéEn informatique théorique, et plus précisément en théorie de la complexité, une classe de complexité est un ensemble de problèmes algorithmiques dont la résolution nécessite la même quantité d'une certaine ressource. Une classe est souvent définie comme l'ensemble de tous les problèmes qui peuvent être résolus sur un modèle de calcul M, utilisant une quantité de ressources du type R, où n, est la taille de l'entrée. Les classes les plus usuelles sont celles définies sur des machines de Turing, avec des contraintes de temps de calcul ou d'espace.
Réseau de trithumb|Un réseau de tri simple composé de quatre fils et cinq connecteurs. En Informatique, un réseau de tri est un algorithme de tri qui trie un nombre fixe de valeurs en utilisant une suite fixe de comparateurs. On peut voir un réseau de tri comme un réseau composé de fils et de comparateurs. Les valeurs, prises dans un ensemble ordonné, circulent le long des fils. Chaque comparateur connecte deux fils, compare les données qui entrent par les fils et les trie, sortant la plus petite donnée sur l'un des fils, la plus grande sur l’autre.
Recherche dichotomiqueLa recherche dichotomique, ou recherche par dichotomie (), est un algorithme de recherche pour trouver la position d'un élément dans un tableau trié. Le principe est le suivant : comparer l'élément avec la valeur de la case au milieu du tableau ; si les valeurs sont égales, la tâche est accomplie, sinon on recommence dans la moitié du tableau pertinente. Le nombre d'itérations de la procédure, c'est-à-dire le nombre de comparaisons, est logarithmique en la taille du tableau.
Complexité en moyenne des algorithmesLa complexité en moyenne d'un algorithme est la quantité d'une ressource donnée, typiquement le temps, utilisée par l'algorithme lors de son exécution pour traiter une entrée tirée selon une distribution donnée. Il s'agit par conséquent d'une moyenne de la complexité, pondérée entre les différentes entrées possibles selon la distribution choisie. Le plus souvent, on ne précise pas la distribution et on utilise implicitement une distribution uniforme (i.e.
Complexité paramétréeEn algorithmique, la complexité paramétrée (ou complexité paramétrique) est une branche de la théorie de la complexité qui classifie les problèmes algorithmiques selon leur difficulté intrinsèque en fonction de plusieurs paramètres sur les données en entrée ou sur la sortie. Ce domaine est étudié depuis les années 90 comme approche pour la résolution exacte de problèmes NP-complets. Cette approche est utilisée en optimisation combinatoire, notamment en algorithmique des graphes, en intelligence artificielle, en théorie des bases de données et en bio-informatique.
Arbre binaire de rechercheEn informatique, un arbre binaire de recherche ou ABR (en anglais, binary search tree ou BST) est une structure de données représentant un ensemble ou un tableau associatif dont les clés appartiennent à un ensemble totalement ordonné. Un arbre binaire de recherche permet des opérations rapides pour rechercher une clé, insérer ou supprimer une clé.
Tri par sélectionLe tri par sélection (ou tri par extraction) est un algorithme de tri par comparaison. Cet algorithme est simple, mais considéré comme inefficace car il s'exécute en temps quadratique en le nombre d'éléments à trier, et non en temps pseudo linéaire. Sur un tableau de n éléments (numérotés de 0 à n-1 , attention un tableau de 5 valeurs (5 cases) sera numéroté de 0 à 4 et non de 1 à 5), le principe du tri par sélection est le suivant : rechercher le plus petit élément du tableau, et l'échanger avec l'élément d'indice 0 ; rechercher le second plus petit élément du tableau, et l'échanger avec l'élément d'indice 1 ; continuer de cette façon jusqu'à ce que le tableau soit entièrement trié.
Algorithme probabilisteEn algorithmique, un algorithme probabiliste, ou algorithme randomisé, est un algorithme qui utilise une source de hasard. Plus précisément le déroulement de l’algorithme fait appel à des données tirées au hasard. Par exemple à un certain point de l’exécution, on tire un bit 0 ou 1, selon la loi uniforme et si le résultat est 0, on fait une certaine action A et si c'est 1, on fait une autre action. On peut aussi tirer un nombre réel dans l'intervalle [0,1] ou un entier dans un intervalle [i..j].
Tri par paquetsLe tri par paquets est un algorithme de tri qui fonctionne sur des nombres réels appartenant à un intervalle borné fixé à l'avance. Le principe de ce tri consiste à partitionner régulièrement l'intervalle d'entrée en autant de sous-intervalles que l'entrée comporte d'éléments à trier, et à distribuer les données selon leur valeurs en autant de paquets correspondant à ces sous-intervalles. Les paquets sont alors triés séparément à l'aide d'un autre algorithme de tri.
Complexité dans le pire des casEn informatique, la complexité dans le pire des cas, ou complexité dans le cas le plus défavorable, mesure la complexité (par exemple en temps ou en espace) d'un algorithme dans le pire des cas d'exécution possibles. Elle est exprimée comme une fonction de la taille de l'entrée de l'algorithme. Implicitement, on cherche à construire des algorithmes s'exécutant en utilisant le moins de ressources possible (e.g. le plus vite possible), et il s'agit par conséquent d'une borne supérieure des ressources requises par l'algorithme.
P (complexité)La classe P, aussi noté parfois PTIME ou DTIME(nO(1)), est une classe très importante de la théorie de la complexité, un domaine de l'informatique théorique et des mathématiques. Par définition, un problème de décision est dans P s'il est décidé par une machine de Turing déterministe en temps polynomial par rapport à la taille de l'entrée. On dit que le problème est décidé en temps polynomial. Les problèmes dans P sont considérés comme « faisables » (feasible en anglais), faciles à résoudre (dans le sens où on peut le faire relativement rapidement).
SortingSorting refers to ordering data in an increasing or decreasing manner according to some linear relationship among the data items. ordering: arranging items in a sequence ordered by some criterion; categorizing: grouping items with similar properties. Ordering items is the combination of categorizing them based on equivalent order, and ordering the categories themselves. In , arranging in an ordered sequence is called "sorting". Sorting is a common operation in many applications, and efficient algorithms have been developed to perform it.
Best, worst and average caseIn computer science, best, worst, and average cases of a given algorithm express what the resource usage is at least, at most and on average, respectively. Usually the resource being considered is running time, i.e. time complexity, but could also be memory or some other resource. Best case is the function which performs the minimum number of steps on input data of n elements. Worst case is the function which performs the maximum number of steps on input data of size n.
NP (complexité)La classe NP est une classe très importante de la théorie de la complexité. L'abréviation NP signifie « non déterministe polynomial » (« en »). Un problème de décision est dans NP s'il est décidé par une machine de Turing non déterministe en temps polynomial par rapport à la taille de l'entrée. Intuitivement, cela revient à dire qu'on peut vérifier « rapidement » (complexité polynomiale) si une solution candidate est bien solution.
