Expliquer la pertinence de la complexité asymptotique des algorithmes dans la pratique de la conception d'algorithmes

40

Dans les algorithmes et la complexité, nous nous concentrons sur la complexité asymptotique des algorithmes, c'est-à-dire la quantité de ressources qu'un algorithme utilise lorsque la taille de l'entrée va à l'infini.

En pratique, nous avons besoin d’un algorithme qui fonctionnerait rapidement pour un nombre fini (bien que possiblement très grand) d’instances.

Un algorithme qui fonctionne bien dans la pratique sur le nombre fini d'instances qui nous intéresse n'a pas besoin d'avoir une bonne complexité asymptotique (une bonne performance sur un nombre fini d'instances n'implique rien en ce qui concerne la complexité asymptotique). De même, un algorithme avec une bonne complexité asymptotique peut ne pas fonctionner correctement sur le nombre fini d'instances qui nous intéresse (par exemple, en raison de la taille des constantes).

Pourquoi utilisons-nous la complexité asymptotique? Comment ces analyses asymptotiques sont-elles liées à la conception d'algorithmes dans la pratique?

Kaveh
la source
Une autre question pertinente est: pourquoi ignorons-nous les facteurs constants ?
Raphaël

Réponses:

24

La question intéressante est: quelle est l'alternative? La seule autre méthode que je connaisse est le test / l'analyse comparative. Nous programmons les algorithmes, les laissons exécuter (sur un échantillon représentatif) l'ensemble d'entrées finies et comparons les résultats. Cela pose quelques problèmes.

  • Les résultats ne sont pas généraux en termes de machines. Exécutez votre test de performance sur un autre ordinateur et vous obtiendrez des résultats différents à coup sûr, quantitativement et peut-être même qualitativement.
  • Les résultats ne sont pas généraux en termes de langages de programmation. Différentes langues peuvent provoquer des résultats très différents.
  • Les résultats ne sont pas généraux en termes de détails de mise en œuvre. Vous comparez littéralement des programmes , pas des algorithmes; de petits changements dans la mise en œuvre peuvent entraîner d’énormes différences de performances.
  • Si le cas le plus défavorable est rare, un échantillon d'entrée aléatoire peut ne pas contenir d'instance incorrecte. Cela est juste si vous êtes préoccupé par les performances moyennes des cas, mais certains environnements exigent des garanties pires.
  • En pratique, les ensembles d'entrées changent. En règle générale, les intrants deviennent plus importants avec le temps. Si vous ne répétez pas votre point de repère tous les six mois (oui, certaines données croissent aussi vite), vos résultats seront bientôt sans valeur¹.

Cela dit, il est typique d’ignorer toutes sortes d’effets et de constantes dans l’analyse, mais on peut parler de paresseux (en ce qui concerne la pratique). Il sert plus à comparer les idées algorithmiques qu’à cerner les performances d’une implémentation donnée (même pseudocode). La communauté sait pertinemment que cela est grossier et qu’il est souvent nécessaire d’examiner de plus près. Par exemple, Quicksort est moins efficace que le type Insertion pour les (très) petites entrées. Pour être juste, une analyse plus précise est généralement difficile ².

Une autre justification, a posteriori, du point de vue formel et abstrait est que, à ce niveau, les choses sont souvent plus claires. Ainsi, des décennies d’études théoriques ont donné lieu à une foule d’idées algorithmiques et de structures de données utiles dans la pratique. L’algorithme théoriquement optimal n’est pas toujours celui que vous souhaitez utiliser en pratique - il faut prendre en compte d’autres considérations, mais il faut améliorer les performances; pense Fibonacci tas - et cette étiquette peut même ne pas être unique. Il est difficile pour un programmeur typique soucieux d'optimiser les expressions arithmétiques de proposer une nouvelle idée à ce niveau (pour ne pas dire que cela n'arrive pas); elle peut (et devrait) effectuer ces optimisations sur l'idée assimilée, cependant.

Il existe des outils théoriques formels pour combler le fossé de la pratique dans une certaine mesure. Des exemples sont

  • compte tenu de la hiérarchie de la mémoire (et des autres E / S),
  • analyser le cas moyen (le cas échéant),
  • analyser le nombre de relevés individuels (au lieu de mesures de coûts abstraites) et
  • déterminant des facteurs constants.

Par exemple, Knuth est connu pour compter littéralement le nombre d'instructions différentes (pour une implémentation donnée dans un modèle donné), permettant ainsi une comparaison précise des algorithmes. Cette approche est impossible sur un plan abstrait et difficile à appliquer dans des modèles plus complexes (pensez à Java). Voir [4] pour un exemple moderne.

Il y aura toujours un fossé entre la théorie et la pratique. Nous travaillons actuellement sur un outil³ dans le but de combiner le meilleur des deux mondes afin de faire des prédictions fiables à la fois pour les coûts algorithmiques et le temps d’exécution (en moyenne), mais nous n’avons pas pu éliminer jusqu’à présent les scénarios dans lesquels un algorithme a une valeur supérieure. coûts d'exécution plus faibles (sur certaines machines) que leurs équivalents (bien que nous puissions le détecter et aider à en trouver la raison).

Je recommande aux praticiens d'utiliser la théorie pour filtrer l'espace des algorithmes avant d'exécuter des tests de performance:

if ( input size forever bounded? ) {
  benchmark available implementations, choose best
  schedule new benchmarks for when machine changes
}
else {
  benchmark implementations of all asymptotically good algorithms
  choose the best
  schedule new benchmarks for when machine changes or inputs grow significantly
}

  1. Il peut y avoir des changements insensés dans les performances absolues et relatives lorsque le nombre d'omissions manquantes dans le cache augmente, ce qui se produit généralement lorsque les entrées augmentent, mais que la machine reste la même.
  2. Comme dans, les principaux chercheurs dans le domaine ne sont pas en mesure de le faire.
  3. Trouvez l'outil ici . Un exemple d'utilisation a été publié dans Dual Pivot Quicksort Using MaLiJAn de Engineering Java 7 par S. Wild et al. (2012) [ preprint ]
  4. Analyse de cas moyenne de Dual Pivot Quicksort de Java 7 par S. Wild et M. Nebel (2012) - [ preprint ]
Raphaël
la source
3
On peut soutenir que le simple fait d'étudier la théorie des algorithmes aiguisera votre œil et formera votre cerveau abstrait aux algorithmes, ce qui vous donnera un autre outil pour évaluer le code dans la programmation quotidienne. Abstenez-vous du code, évaluez le principe, améliorez-le et traduisez-le en code. Exemple: "Ah, je vois, vous voulez programmer un dictionnaire. Mais vous programmez essentiellement des listes; pourquoi ne pas essayer les arbres?"
Raphaël
Les limites de l'analyse asymptotique deviennent évidentes une fois que vous creusez plus profondément; Quicksort est un exemple marquant .
Raphaël
1
FWIW, j'ai écrit un portrait plus récent de mes opinions sur la notation Landau ici .
Raphaël
11

Je suppose que cette question découle de l’enseignement d’un cours comportant une analyse asymptotique. Il y a plusieurs réponses possibles pour expliquer pourquoi ce matériel est enseigné dans les cours d'introduction:

  • L'analyse asymptotique est une abstraction mathématique qui se livre à l'analyse. En tant que mathématiciens, nous voulons pouvoir analyser des algorithmes, et le seul moyen d’apprivoiser leur complexité consiste à utiliser une analyse asymptotique.

  • L'évaluation de la performance asymptotique d'un algorithme met en évidence certains principes utiles en pratique: par exemple, concentrez-vous sur la partie du code qui prend la majorité du temps et mettez à l'écart toute partie du code qui prend une partie du temps asymptotiquement négligeable. .

  • Certaines des techniques d'analyse asymptotique sont utiles. Je parle ici principalement du "théorème maître", qui dans de nombreuses circonstances est une bonne description de la réalité.

  • Il y a aussi une raison historique: quand les gens ont commencé à analyser des algorithmes, ils ont pensé sérieusement que la complexité asymptotique reflétait une utilisation pratique. Cependant, ils se sont finalement avérés faux. La même chose s’est produite avec P en tant que classe de problèmes pouvant être résolus efficacement, et NP en tant que classe de problèmes insolubles, qui sont en pratique trompeurs.

Personnellement, je pense que l'analyse asymptotique est une partie raisonnable du programme. Les parties les plus discutables incluent la théorie du langage formel et la théorie de la complexité (tout ce qui concerne une machine de Turing). Certaines personnes avancent que si ces sujets ne sont pas utiles en soi au programmeur, ils lui inculquent une certaine pensée qui est nécessaire pour être un bon praticien. D'autres soutiennent que la théorie influence parfois la pratique et que ces rares cas suffisent à justifier l'enseignement de ces sujets plutôt obscurs au grand public de l'informatique. Je préférerais qu'ils apprennent l'histoire, la littérature ou tout autre sujet qui les intéresse réellement; les deux sont aussi pertinents pour leurs perspectives d'emploi futures et plus importants pour eux en tant qu'êtres humains.

Yuval Filmus
la source
Merci Yuval. La motivation principale est de savoir comment expliquer aux étudiants l’utilité de l’analyse asymptotique et sa pertinence pour la pratique de la conception et de l’utilisation d’algorithmes dans des applications réelles très grand nombre d’occurrences), ne justifiant pas le programme.
Kaveh
1
Je suis confus par votre prémisse. Vous semblez supposer que le groupe cible est composé à la fois de mathématiciens et de programmeurs en herbe, ce qui est une combinaison étrange et qui ne caractérise pas les informaticiens. (Je ne partage pas non plus votre point de vue sur les langages formels, mais c'est un autre sujet.)
Raphael
Au contraire, je suppose que le groupe cible est constitué de futurs programmeurs. Cependant, une grande partie du programme est là pour les informaticiens théoriques. Bien entendu, ces deux groupes ont des besoins contradictoires. Étant donné que la plupart des étudiants de premier cycle sont des programmeurs potentiels, je pense que le programme d’enseignement devrait être conçu en fonction de ces programmes, mais certains universitaires ne sont pas d’accord. Peut-être qu'ils veulent enseigner aux futurs professeurs. Peut-être que vous pouvez expliquer leur point de vue.
Yuval Filmus
3
@YuvalFilmus J'ai souvent expliqué que je ne croyais pas que CS = TCS + Programming. Si vous enseignez un cours de CS (dans une université) et que la plupart de vos étudiants veulent être des programmeurs, quelque chose ne fonctionne pas (à mon humble avis). Je dirais que n'importe quel informaticien peut tirer profit d'une solide formation en algorithmique, en langages formels et même en théorie de la complexité (et bien d'autres choses, comme le fonctionnement des compilateurs et des processeurs).
Raphaël
2
@Wildcard Architecture informatique, infographie, IA, recherche en langage de programmation, ... la liste est interminable! Le SDC est vraiment un créneau et la programmation n’est qu’un outil pour la plupart des chercheurs en informatique.
Raphaël
7

L’utilisation de l’analyse asymptotique des temps d’exécution a deux raisons sérieuses:

  • n

  • pour permettre la traçabilité mathématique. Les cas tels qu'il est possible de trouver des expressions exactes pour le nombre d'opérations sont exceptionnels. L'étude des asymptotiques ouvre plus de possibilités (comme les approximations asymptotiques de fonctions compliquées sont pratiques).

Et il y en a beaucoup d'autres (comme l'indépendance de la machine, le sens, la comparabilité, etc.).

Yves Daoust
la source
n
Eh bien, je ne pense pas que ce soit une règle du tout. Plus vous jetez de données, plus les déclarations que vous pouvez faire sont faibles. La perspective asymptotique (et, plus encore, "big-oh") crée des instructions telles que "Quicksort est plus rapide que Insertionsort", ce qui est sinon faux, pas tout à fait vrai non plus. (Oui, je dis que l'analyse des algorithmes est souvent mal enseignée, à mon humble avis.)
Raphael
6

Comme indiqué dans la réponse de Raphaël, il peut être très difficile de calculer avec exactitude la durée d'exécution la plus défavorable. Le calcul exact peut également être inutile puisque le modèle RAM introduit déjà des approximations. Par exemple, toutes les opérations prennent-elles vraiment le même temps? Des implémentations spécifiques (matériel, optimisations) peuvent accélérer un algorithme par des facteurs constants. Nous voulons comprendre l'efficacité d'un algorithme indépendamment de ces facteurs. C'est une grande motivation pour l'utilisation de l'analyse asymptotique.

Juho
la source
3

Parce que les asymptotiques sont "simples" (enfin, plus simples que de faire l'analyse exacte pour les cas finis, en tout cas).

Comparez, par exemple, l'encyclopédie "The Art of Computer Programming" de Knuth, qui analyse en détail tous les algorithmes importants (et de nombreux algorithmes moins importants) avec l'analyse de règle empirique qui est souvent suffisante pour obtenir une estimation asymptotique ( ou simplement une limite), comme pratiqué dans la plupart des livres "d'algorithmes".

Vous avez certainement raison. Si le problème est suffisamment important, une analyse de type Knuth (ou peut-être un peu moins détaillée) pourrait bien être justifiée. Dans de nombreux cas, un indice de la complexité asymptotique (peut-être moyenne avec dispersion) ajusté aux données expérimentales est suffisant. Dans la plupart des cas , une classification approximative des algorithmes en concurrence, en tant que premier tour complet, en comparant les asymptotiques peut être suffisamment précise. Et s’il n’ya pas de prétendants, le masochisme est ce qu’il ya de mieux en ce qui concerne le coût exact.

vonbrand
la source
2
Ce n’est que la moitié de la vérité: d’abord, il semble que vous écriviez en pensant au "gros-oh" (que la question ne mentionne pas). Deuxièmement, les asymptotiques "big-oh" sont connus pour leurs échecs spectaculaires lors de la sélection d'algorithmes: les entrées sont finies en réalité.
Raphaël
3

Ici, par analyse asymptotique, je suppose que nous entendons le comportement de l’algorithme lorsque la taille de l’entrée va à l’infini.

Nous utilisons l'analyse asymptotique parce qu'elle est utile pour prédire le comportement des algorithmes en pratique . Les prédictions nous permettent de prendre des décisions, par exemple lorsque nous avons différents algorithmes pour un problème, lequel devons-nous utiliser? (Être utile ne veut pas dire que c'est toujours correct.)

La même question peut être posée à propos de tout modèle simplifié du monde réel. Pourquoi utilisons-nous des modèles mathématiques simplifiés du monde réel?

Pensez à la physique. La physique newtonienne classique n’est pas aussi bonne que la physique relativiste pour prédire le monde réel. Mais c’est un modèle suffisant pour la construction de voitures, de gratte-ciel, de sous-marins, d’avions, de ponts, etc. Dans certains cas, cela ne suffit pas, par exemple si nous voulons construire un satellite ou envoyer une sonde spatiale à Pluton ou prévoir le mouvement. des objets célestes massifs comme les étoiles et les planètes ou des objets à très grande vitesse comme les électrons. Il est important de savoir quelles sont les limites d'un modèle.

  1. C'est typiquement une assez bonne approximation du monde réel. En pratique, nous voyons souvent qu’un algorithme avec une meilleure analyse asymptotique fonctionne mieux dans la pratique. Il est rare qu'un algorithme ait un meilleur comportement asymptotique. Ainsi, si les entrées peuvent être assez grandes, nous pouvons généralement nous baser sur une analyse asymptotique comme première prédiction du comportement des algorithmes. Ce n'est pas le cas si nous savons que les intrants vont être réduits. En fonction de la performance souhaitée, nous pouvons être amenés à effectuer une analyse plus minutieuse. Par exemple, si nous disposons d'informations sur la distribution des entrées, nous pouvons effectuer une analyse plus minutieuse pour atteindre les objectifs que nous avons définis. % d'intrants). L’analyse asymptotique est un bon point de départ. En pratique, nous devrions également faire des tests de performance, mais gardez à l'esprit que cela a aussi ses propres problèmes.

  2. UNEUNEUNEa une meilleure complexité asymptotique. Qu'est-ce qu'aucun d'entre eux n'est meilleur que l'autre dans tous les intrants? Cela devient alors plus délicat et dépend de nos préoccupations. Est-ce que nous nous soucions des grands ou petits intrants? Si nous nous soucions des grandes entrées, il n’est pas courant qu’un algorithme ait une meilleure complexité asymptotique, mais se comporte le moins possible sur les grandes entrées qui nous intéressent. Si nous nous soucions davantage des petits intrants, l’analyse asymptotique pourrait ne pas être très utile. Nous devrions comparer la durée d'exécution des algorithmes sur les entrées qui nous intéressent. En pratique, l'analyse asymptotique peut ne pas être aussi utile pour des tâches complexes avec des exigences complexes. C'est très utile pour les problèmes de base simples abordés dans les manuels d'algorithmes.

En résumé, la complexité asymptotique est une approximation relativement facile de la complexité réelle des algorithmes pour des tâches de base simples (problèmes dans un manuel d’algorithmes). Au fur et à mesure que nous élaborons des programmes plus complexes, les exigences de performances changent et deviennent de plus en plus complexes. Une analyse asymptotique peut ne pas être aussi utile.


Il est bon de comparer l'analyse asymptotique à d'autres approches permettant de prédire la performance d'algorithmes et de les comparer. Les tests de performance par rapport à des entrées aléatoires ou de référence constituent une approche courante. Il est courant que le calcul de la complexité asymptotique soit difficile ou irréalisable, par exemple lorsque nous utilisons des méthodes heuristiques, comme par exemple la résolution SAT. Un autre cas de figure est celui où les exigences sont plus complexes, par exemple lorsque les performances d’un programme dépendent de facteurs extérieurs et que notre objectif peut être d’obtenir quelque chose qui se termine dans des délais déterminés (par exemple, pensez à mettre à jour l’interface affichée à un utilisateur) sur 99% des utilisateurs. contributions.

Mais gardez à l'esprit que l'analyse de la performance a aussi ses problèmes. Nous n'effectuons pas le test de performance sur toutes les entrées qui seront données à l'algorithme (souvent infaillibles sur le plan informatique) (et il est souvent impossible de décider que certaines entrées ne seront jamais données). Si nous testons sur un échantillon aléatoire ou un point de référence, nous supposons implicitement une certaine régularité concernant les performances des algorithmes, autrement dit, l'algorithme fonctionnera de la même manière sur d'autres entrées qui ne faisaient pas partie du test de performance.

Le deuxième problème avec les tests de performance est qu'ils dépendent de l'environnement de test. Par exemple, les performances d’un programme ne dépendent pas uniquement des entrées, mais de facteurs extérieurs (type de machine, système d’exploitation, efficacité de l’algorithme codé, utilisation de la CPU, temps d’accès à la mémoire, etc.), dont certains peuvent varier entre différentes exécutions de programmes. le test sur la même machine. Ici encore, nous supposons que les environnements particuliers testés sont similaires à l'environnement réel, à moins que nous ne fassions les tests de performance sur tous les environnements sur lesquels nous pouvons exécuter le programme (et comment pouvons-nous prédire sur quelles machines une personne peut exécuter un tri) algorithme dans 10 ans?).

Θ(nlgn)Θ(n2)Θ(lgn)O(n)

Kaveh
la source
Continuons cette discussion sur le chat .
Raphaël
J'aime cette réponse assez pour upvote maintenant. Deux notes: 1) Je voudrais utiliser "coût" au lieu de "complexité" ici. En partie pour des raisons liées à la présence d'animaux domestiques, mais aussi parce qu'il existe de nombreuses mesures de coûts imaginables (ce qui complique toutes les considérations que vous mentionnez). 2) Vous voudrez peut-être faire un laissez-passer linguistique. ;)
Raphael
@ Raphaël, merci. Je prévois de faire une autre édition bientôt. :)
Kaveh
-2

O(n2)O(nbûchen)O(n2) pour qu'il se termine par rapport à quicksort.

Imaginez maintenant que l' attente soit répétée dans le code autant de fois que le code est appelé. comment quantifier / justifier mathématiquement cette supériorité apparente de l'algorithme quicksort? (C'est-à-dire que son nom est vraiment justifié ou s'agit-il simplement d'un slogan marketing?) via des mesures de complexité asymptotiques. il suffit de regarder les animations subjectivement pour penser que bubbleort est en quelque sorte un algorithme plus faible et une analyse asymptotique de la complexité peut le prouver quantitativement. mais notez que l’analyse asymptotique de la complexité n’est qu’un outil parmi d’autres pour analyser des algorithmes et qu’elle n’est pas toujours optimale.

et sa vaut la peine de regarder le code côte à côte également. Bubblesort semble être conceptuellement plus simple et n'utilise pas de récursivité. quicksort n’est pas immédiatement compris, en particulier le principe de pivot "médian de 3". Bubblesort peut être implémenté uniquement dans les boucles sans sous-programme, alors que QuickSort peut généralement avoir au moins un sous-programme. Cela montre à quel point une sophistication accrue du code peut parfois améliorer la complexité asymptotique au détriment de la simplicité du code. il existe parfois un compromis extrême similaire au concept de rendements marginaux décroissants (provenant de l’économie), où de très grandes quantités de complexité de code [exigeant des papiers entiers pleins de preuves et de preuves pour justifier] n’achètent que de très petites améliorations de la complexité asymptotique. cela apparaît à titre d'exemple esp avecmultiplication matricielle et peut même être représentée graphiquement .

vzn
la source
Il y a beaucoup de terrain entre "regarder des animations" et une analyse formelle, telle que des repères d'exécution étendus. Ils constituent en fait un domaine valide, car nous n’avons pas de théorie pour expliquer tout ce qui influence les temps d’exécution.
Raphaël
@raphael vous avez couvert l'analyse comparative dans votre réponse; c'est une bonne réponse. mais notez que l'animation / visualisation peut être étroitement liée à l'analyse comparative. en fait, il y a beaucoup d'explications sur ce qui influence les durées d'exécution [couvertes dans d'autres réponses] mais dans une certaine mesure, son "bruit" et sa complexité asymptotique "atténue / atténue le bruit". C’est un autre exercice pour voir comment il fait cela.
vzn
Les animations ne filtrent pas le bruit, cependant. De plus, l’œil humain est facilement dupé, et il n’est tout simplement pas possible de regarder des animations pour un échantillon de taille raisonnable de listes de taille raisonnable (par exemple, 1 000 listes pour des tailles dans des millions d’algorithmes de tri comparatifs) et de choisir l’algorithme le plus rapide. (en moyenne).
Raphaël
nn
n