Traitant de la complexité des algorithmes - les nuls

Partie des algorithmes pour les nuls Triche

Vous savez déjà que les algorithmes sont complexes. Cependant, vous devez savoir à quel point un algorithme est complexe car plus il est complexe, plus il faut de temps pour s'exécuter. Le tableau suivant vous aide à comprendre les différents niveaux de complexité présentés par ordre de durée (du plus rapide au plus lent).

Complexité	Description
Complexité constante O (1)	Fournit un temps d'exécution constant, quelle que soit la quantité de données que vous fournissez. Chaque entrée nécessite une seule unité d'exécution.
Complexité logarithmique O (log n)	Le nombre d'opérations augmente plus lentement que l'entrée, ce qui rend l'algorithme moins efficace avec de petites entrées et plus efficace avec de plus grandes. Un algorithme typique de cette classe est la recherche binaire.
Complexité linéaire O (n)	Les opérations augmentent avec l'entrée dans un rapport de 1: 1. Un algorithme typique est l'itération, lorsque vous scannez une entrée une fois et que vous appliquez une opération à chaque élément de celle-ci.
Complexité linéarithmique O (n log n)	La complexité est un mélange de complexité logarithmique et linéaire. Il est typique de certains algorithmes intelligents utilisés pour commander des données, tels que Mergesortsort, Heapsort et Quicksort.
Complexité quadratique O (n 2 )	Les opérations se développent comme un carré du nombre d'entrées. Lorsque vous avez une itération dans une autre itération (appelée itérations imbriquées en informatique), vous avez une complexité quadratique. Par exemple, vous avez une liste de noms et, afin de trouver les plus similaires, vous comparez chaque nom à tous les autres noms. Certains algorithmes d'ordonnancement moins efficaces présentent une telle complexité: le tri à bulles, le tri par sélection et le tri par insertion. Ce niveau de complexité signifie que vos algorithmes peuvent fonctionner pendant des heures voire des jours avant d'atteindre une solution.
Complexité cubique O (n 3 )	Les opérations se développent encore plus vite que la complexité quadratique car vous avez maintenant plusieurs itérations imbriquées. Lorsqu'un algorithme a cet ordre de complexité et que vous devez traiter une quantité modeste de données (100 000 éléments), votre algorithme peut fonctionner pendant des années. Lorsque vous avez un nombre d'opérations qui est une puissance de l'entrée, il est courant de se référer à l'algorithme comme étant en cours d'exécution en temps polynomial.
Complexité exponentielle O (2 n )	L'algorithme prend deux fois le nombre d'opérations précédentes pour chaque nouvel élément ajouté. Lorsqu'un algorithme a cette complexité, même de petits problèmes peuvent prendre une éternité. De nombreux algorithmes effectuant des recherches exhaustives ont une complexité exponentielle. Cependant, l'exemple classique pour ce niveau de complexité est le calcul des nombres de Fibonacci.
Complexité factorielle O (n!)	Cet algorithme présente un véritable cauchemar de complexité en raison du grand nombre de combinaisons possibles entre les éléments. Imaginez: si votre entrée est de 100 objets, et qu'une opération sur votre ordinateur prend 10 -6 secondes (une vitesse raisonnable pour chaque ordinateur de nos jours), vous aurez besoin d'environ 10 140 années accomplir la tâche avec succès (une durée impossible car l'âge de l'univers est estimé à 10 14 ans). Un problème de complexité factorielle célèbre est le problème du voyageur de commerce, dans lequel un vendeur doit trouver le chemin le plus court pour visiter de nombreuses villes et revenir à la ville de départ.