Divers

Complexité temporelle: pourquoi certains algorithmes fonctionnent pendant des milliards d'années

Complexité temporelle: pourquoi certains algorithmes fonctionnent pendant des milliards d'années

Ceci est le troisième article d'une série en sept parties sur les algorithmes et le calcul, qui explore la façon dont nous utilisons des nombres binaires simples pour alimenter notre monde. Le premier article, Comment les algorithmes gèrent le monde dans lequel nous vivons, peut être trouvé ici.

Si vous regardez une visualisation de différents algorithmes de tri travaillant sur un ensemble de données, il devient très évident, très rapidement, que certains sont bien meilleurs que d'autres. Où un algorithme mène secondes pour terminer, un autre prendra minutes même avec de petits ensembles de données. Heureusement, nous n'avons pas besoin de voir l'algorithme au travail pour savoir si l'algorithme peut faire le travail rapidement ou s'il va s'effondrer sous le poids de son entrée. C'est quoi Notation Big O est pour, et il peut nous dire en un coup d'œil si le Complexité temporelle d'un algorithme signifie que nous l'obtiendrons dans quelques heures ou milliards d'années.

Qu'est-ce que la complexité du temps?

En termes plus formels, complexité temporelle est la mesure du temps nécessaire à un algorithme pour produire un résultat, par rapport à la taille de son entrée. Pratiquement, c'est le taux de croissance dans le nombre d'opérations nécessaire pour produire un résultat pour chaque unité supplémentaire d'entrée.

Dans le premier article de cette série, j'ai décrit un simple algorithme de sommation. Pour calculer le somme de tous les nombres entre les nombres p et q, J'ai déclaré une autre variable, r, et réglez-le sur zéro. J'ai ensuite ajouté p à r, puis j'ai ajouté p + 1 à r, puis p + 2, et ainsi de suite jusqu'à ce que j'aie finalement ajouté q lui-même à r, à quel point je me suis arrêté et j'ai renvoyé le résultat, r, qui a tenu le somme.

Combien d'opérations cela nécessitera, sans savoir quelle sera la taille d'entrée ultime, en utilisant uniquement les variables abstraites p et q? Ce que nous faisons réellement, c'est exécuter un boucle où chaque itération augmente p par exactement 1 et l'ajoute r. C'est en fait à quoi ressemble notre algorithme lorsqu'il est présenté un peu plus formellement:

1. laisser r = 0
2. pendant p est <= à q
3. r=p+r
4. p = p+1
5. retour r

Lorsqu'il est présenté comme ça dans ce que nous appelons pseudocode, il devient beaucoup plus facile de voir combien d'opérations cela prendra. Descendez les étapes numéro par numéro et comptez les opérations. Le premier est une instruction, donc c'est une seule opération. La deuxième ligne, cependant, est différente. Des boucles comme celle-ci se répètent jusqu'à ce que la condition soit satisfaite, dans ce cas, une fois p est supérieur à q. Nous savons alors que nous incluons q et p dans le somme, donc le nombre de itérations à travers cela boucle est égal à q - (p - 1), qui est le taille d'entrée pour notre algorithme.

Mais c'est juste le nombre de fois que nous itérons dans la boucle, nous devons également compter les opérations à l'intérieur, c'est là que nous ajoutons p et r et attribuer le résultat à r puis on ajoute p et 1 puis attribuez le résultat à p. Alors on joue deux opérations pour chaque itération, et il y a q - (p - 1)itérations. Il ne nous reste plus qu'à multiplier 2 opérations et q - (p - 1)itérations obtenir 2 * (q - (p - 1)) opérations pour toute la boucle. Ajoutez les opérations en 1. et 5., ce qui nous donne un décompte final de 2 * (q - (p - 1)) + 2 opérations pour cet algorithme.

C'est une fonction linéaire car il n'y a pas d'exposants, donc le taux de croissance car notre algorithme de sommation est directement lié à la contribution taille, que nous appelons complexité temporelle linéaire. En règle générale, quel que soit le terme d'ordre le plus élevé d'une formule qui définit notre complexité temporelle, c'est ce qui caractérise sa croissance dans le temps, nous prenons donc le terme d'ordre le plus élevé et supprimons le reste, laissant q - (p - 1), ce que nous appel n par souci de simplicité.

La complexité temporelle linéaire peut sembler inefficace lorsque vous imagez des tailles d'entrée dans les milliards, mais le temps linéaire n'est pas vraiment trop mauvais. Nous pouvons faire mieux cependant.

Nous savons depuis très longtemps que le somme de toutles nombres de 1 et q est donné par la formule (q * (q + 1)) / 2. Nous savons également que lepropriété commutative d'addition nous dit que le résultat de (p-1 * (p)) / 2 soustrait de (q * (q + 1)) / 2 supprime simplement la partie de la somme qui comprend tout de 1 à p-1, quittant le somme des nombres de p à q derrière, c'est exactement ce que nous voulons.

Cet algorithme, selon la façon dont il est codé, ne devrait pas prendre plus de trois opérations. Étant donné que les opérations mathématiques directes comme celle-ci sont exactement ce que les ordinateurs font mieux que les humains, nous pourrions enchaîner les formules en une seule expression mathématique, et le processeur la mâchera aussi facilement que si nous la divisions en plus petits morceaux, mais nous nous en tiendrons à trois opérations pour le moment.

1. p = (p-1 * (p)) / 2
2. q
= (q * (q + 1)) / 2
3. revenir ( q -p )

Non boucles, juste un nombre constant d'opérations qui ne changent pas, quelle que soit la différence entre p et q est. Cet algorithme prendra toujours trois opérations à effectuer, nous appelons donc cela complexité en temps constant.

Maintenant, si vous ne saviez pas ce que vous taille d'entrée allait être lorsque vous conceviez un algorithme, quel algorithme allez-vous utiliser entre ces deux? De toute évidence, le deuxième, car algorithmes à temps constant sont essentiellement un déjeuner gratuit de calcul en ce qui concerne l'entrée. Alors comme nous Augmenter notre programme pour gérer plus de données, leur temps d'exécution ne changera pas de manière appréciable, alors que nous savons que notre premier algorithme augmentera exactement autant que notre entrée, qui pourrait être une valeur de plusieurs milliards ou plus. Bien sûr, la complexité temporelle constante ne signifie pas toujours qu'elle est plus efficace, mais dans ce cas, c'est celle que nous voulons.

Avant de nous asseoir pour écrire un ligne de code, nous avons déjà compris quel algorithme était la meilleure option pour notre contribution, et nous n'avons jamais eu à l'exécuter pour savoir comment cela fonctionne. C'est pourquoi nous utilisons complexité temporelle, il n'y a tout simplement pas autant d'outils qui soient aussi efficaces évaluer l'efficacité des algorithmes.

Qu'est-ce que la notation Big O?

Nous avons une manière spéciale d'annoter cette efficacité pour faciliter les choses, ce que nous appelons Notation Big O. Tout simplement, Notation Big O représente le algorithmeEfficacité courir à travers son pire scénario. Si vous deviez rechercher un nom dans un répertoire en lisant chaque nom jusqu'à ce que vous trouviez le bon, le pire des cas est que le nom que vous voulez soit la toute dernière entrée du répertoire. Cela signifie que vous devrez lire tout le répertoire de n noms pour accéder à celui que vous voulez. Nous disons donc que cet algorithme est O (n), où n est le terme d'ordre le plus élevé dans notre formule d'exploitation.

Il y a d'autres Grandes notations pour le meilleur cas et cas moyen, mais ce qui compte vraiment, c'est le pire scénario; ce sont ceux qui peuvent planter votre ordinateur - ou pire, ta voiture ou ton avion. Ils vont droit au cœur du pourquoi complexité temporelle compte et expliquez pourquoi quelques algorithmes ne peut tout simplement pas résoudre un problème sans prendre quelques milliards d'années pour le faire.

Alors, comment utilisons-nous Notation Big O? Le tableau ci-dessus vous montre comment ces différents Notations Big O regardez en pratique, avec le axe x étant votre contribution et votre axe y le temps nécessaire pour terminer. Pour un peu plus de détails, vous trouverez une liste rapide de tous les Notations Big O qui comptent pour le moment et le complexité temporelle ils représentent:

* O (1): Complexité en temps constant- Il s'agit de la passe gratuite de calcul efficace dont nous avons parlé auparavant. Cela ne signifie pas nécessairement que c'est plus rapide. Cela signifie simplement que le complexité temporelle n'a aucun rapport avec la taille de l'entrée.

* O (log n): Complexité temporelle logarithmique- Ce sont les plus courants lors de l'utilisation d'un stratégie de division et de conquête sur un ensemble de données, où chaque opération rejette une grande partie de l'entrée qu'elle a exclue comme n'ayant pas la solution. L'exemple classique consiste à rechercher un mot dans un dictionnaire: ouvrez au hasard, vérifiez dans quelle section de lettre vous vous trouvez, puis ignorez la partie où vous savez que votre mot ne sera pas, et subdivisez et supprimez de manière récursive les sections restantes jusqu'à ce que vous trouviez ta parole.

* Sur): Complexité temporelle linéaire- C'était notre algorithme de sommation depuis le début.

* O (n log n): Complexité temporelle linéarithmique- Effectuer une transformation de Fourier rapide est un O (n Log n) algorithme, tout comme un Mergesort.

* Sur2): Complexité temporelle quadratique- Cela se trouve généralement chaque fois que vous avez des boucles imbriquées. Dans notre premier algorithme, si nous avions une deuxième boucle dans la première, la fonction aurait développé une complexité temporelle quadratique.

* Surc, c> 1): Complexité temporelle polynomiale- Complexité temporelle polynomiale est très important parce que c'est plus ou moins représente la limite supérieure sur quoi ordinateur classique peut résoudre dans un laps de temps pratique.

* O (cn, n> 1, c> 1): Complexité temporelle exponentielle- C'est là que vous commencez à obtenir le Algorithmes de plusieurs milliards d'années. À tout moment unité d'entrée vous fait doubler le nombre d'opérations effectuées par rapport au nombre qui sont exécutés si l'entrée estn-1, vous avez complexité temporelle exponentielle. L'exemple le plus courant que la plupart des gens utilisent est d'essayer d'énumérer chaque sous-ensemble possible d'un ensemble, mais Forçage brutal une Clé de cryptage 128 bits est généralement classé dans cette catégorie.

* Sur!): Complexité temporelle factorielle- Ce sont des algorithmes qui pourraient probablement fonctionner jusqu'à la mort thermique de l'Univers avec une taille d'entrée modérément grande de quelques milliers. Chaque fois que vous avez quelque chose comme «de combien de façons différentes pouvez-vous organiser cette séquence», vous avez un problème de permutation et forcer votre chemin vers une réponse nécessite de créer n! valeurs différentes, qui sont données par le résultat de: n * (n - 1) * (n - 2) * ... * 3 * 2 * 1. Ce sont les algorithmes qui fonctionnent presque parallèlement au axe y dans le diagramme ci-dessus.

Pourquoi nous ne pouvons pas simplement proposer de meilleurs algorithmes

Ce n’est pas faute d’essayer. L'ensemble du domaine de informatique théorique il s'agit d'essayer de trouver le plus algorithme efficace pour un problème donné, mais parfois nous ne connaissons tout simplement pas le calcul. Et pas seulement vous et moi, nous parlons des gagnants de la médaille Field’s qui ont rencontré des problèmes comme le O (2n) et Sur!) et leur estimation est aussi bonne que la nôtre.

Il y a tout un catalogue de problèmes que nous n'avons pas encore les calculs à résoudre - nous y reviendrons plus avant vers la fin de la série -, mais ces problèmes agissent comme des points d'étranglement qui créent des inefficacités dans les affaires, la recherche scientifique et autres les zones administratives, et il y a beaucoup de gens qui attendent que ces problèmes soient enfin résolus. Des prix très lucratifs ont même été offerts à quiconque peut résoudre certaines de ces choses, mais jusqu'à présent, personne n'a pu le faire et certains de ces problèmes persistent depuis des décennies.

La raison pour laquelle ordinateurs classiques ne peut pas résoudre ces problèmes efficacement non plus est intégré dans les circuits de la machine; chaque instruction donnée doit être complétée avant de pouvoir commencer sur la suivante. Les systèmes multicœurs ou les machines multiprocesseurs peuvent accélérer les choses, mais vous en auriez probablement encore besoin un ou deux mille milliards d'années pour obtenir un résultat après avoir jeté tous nos processeurs ensemble et les avoir libérés sur un Sur!) problème où n était quelque chose comme 500.

Les ingénieurs en informatique ont vu cela venir pendant des décennies, mais maintenant nous arrivons enfin à la fin de la ligne pour ce que nous pouvons tirer d'un ordinateur classique. Tu ne peux juste pas faire ça les opérations vont plus vite, et par nature, ils peuvent effectuer une seule opération à la fois. Si vous avez un algorithme qui nécessite quintillions d'opérations pour terminer, un ordinateur classique doit effectuer tous ces opérations dans l'ordre. À ce stade, le temps qu'il faut pour obtenir un résultat devient simplement une question de maths et physique. Si nous voulons résoudre ces problèmes qui ont complexité temporelle exponentielle ou supérieure, puis autre chose est nécessaire.

La bonne nouvelle est que nous savons que c’est possible, en au moins un cas, pour trouver un algorithme suffisamment efficace pour trouver la réponse à l'une de ces O (2n) problèmes dans complexité temporelle polynomiale. Si cela peut être fait une fois, alors il est possible de le faire à nouveau; ça prend juste contourner le problème de la «physique».

Le quatrième article de notre série sur les algorithmes et le calcul, Comment l'algorithme de Peter Shor met en échec le chiffrement RSA, peut être trouvé ici.


Voir la vidéo: Pour faire naître une idée - Cédric Villani, à lUSI (Octobre 2021).