En quoi est-elle différente de l'analyse asymptotique ? Quand l'utilisez-vous, et pourquoi ? J'ai lu quelques articles qui Semblent avoir été bien écrits comme ceux-ci :
http://www.ugrad.cs.ubc.ca/~cs320/2010W2/documents/aa-nutshell.pdf
http://www.cs.princeton.edu/~fiebrink/423/AmortisedAnalysisExplained_Fiebrink.pdf
...mais je suis peut-être stupide, alors quelqu'un peut-il me simplifier la tâche ?
L'analyse amortie ne multiplie pas naïvement le nombre d'invocations avec le pire cas pour une invocation.
Par exemple, pour un tableau dynamique qui double de taille en cas de besoin, une analyse asymptotique normale conclurait seulement que l'ajout d'un élément à ce tableau coûte O(n), car il peut être nécessaire de croître et de copier tous les éléments dans le nouveau tableau. L'analyse asymptotique tient compte du fait que pour avoir à croître, n/2 éléments doivent avoir été ajoutés sans causer de croissance depuis la croissance précédente, donc ajouter un élément ne prend réellement que O(1) (le coût de O(n) est de amorti sur n/2 actions).
L'analyse amortie n'est pas la même chose qu'une "performance moyenne" - l'analyse amortie donne une garantie absolue sur ce que la performance fera si vous faites tant d'actions.
Il y a beaucoup de réponses au quoi, mais aucune au pourquoi.
Comme tout le monde l'a dit, l'analyse asymptotique concerne la façon dont la performance d'une opération donnée s'adapte à un grand ensemble de données. L'analyse amortie s'intéresse à l'évolution de la moyenne des performances de toutes les opérations sur un grand ensemble de données. L'analyse amortie ne donne jamais de limites plus mauvaises que l'analyse asymptotique, et en donne parfois de bien meilleures.
Si vous êtes concerné par le temps d'exécution total d'un travail plus long, les meilleures limites de l'analyse amortie sont probablement ce qui vous intéresse. C'est pourquoi les langages de script (par exemple) sont souvent heureux de faire croître les tableaux et les tables de hachage par un certain facteur, même si c'est une opération coûteuse. (La croissance peut être un O(n) opération, mais amortis est O(1) parce que vous le faites rarement).
Si vous faites de la programmation en temps réel (les opérations individuelles doivent se terminer dans un temps prévisible), alors les meilleures limites de l'analyse amortie n'ont pas d'importance. Peu importe que l'opération ait été rapide en moyenne, si vous n'avez pas réussi à la terminer à temps pour revenir en arrière et régler la scie à ruban avant qu'elle ne coupe trop loin...
Le choix de l'une ou l'autre dépend de la nature exacte de votre problème de programmation.
Ce terme se réfère à l'analyse des performances d'un algorithme en supposant que les données sur lesquelles l'algorithme opère (les données de base) sont les mêmes que celles de l'algorithme. entrée ) est, en termes simples, "suffisamment grande pour que le fait de l'augmenter ne change pas la conclusion". Bien que la taille exacte de l'entrée n'ait pas besoin d'être spécifiée (nous n'avons besoin que d'une limite supérieure), l'ensemble de données en soi a à spécifier.
Notez que jusqu'à présent, nous n'avons parlé que de l'élément méthode d'analyse ; nous n'avons pas spécifié exactement quelle quantité que nous analysons (complexité temporelle ? complexité spatiale ?), et nous n'avons pas non plus spécifié quelle est la nature de l'analyse. métrique qui nous intéressent (pire cas ? meilleur cas ? moyenne ?).
Dans la pratique, le terme d'analyse asymptotique fait généralement référence à limite supérieure de la complexité temporelle d'un algorithme, c'est-à-dire la performance la plus défavorable mesurée par le temps d'exécution total, qui est représentée par la notation big-Oh (par exemple, un algorithme de tri peut être O(nlogn) ).
Ce terme désigne l'analyse des performances d'un algorithme sur la base d'une séquence spécifique d'opérations qui vise à atteindre les objectifs suivants scénario le plus défavorable -- En d'autres termes, l'analyse amortie implique que la mesure correspond à la performance dans le pire des cas (bien qu'elle ne précise toujours pas quelle quantité est mesurée). Pour effectuer cette analyse, nous devons spécifier le paramètre taille de l'entrée, mais nous n'avons pas besoin de faire d'hypothèses sur sa forme.
En termes simples, l'analyse amortie consiste à choisir une taille arbitraire pour l'entrée, puis à "jouer" avec l'algorithme. Chaque fois qu'une décision qui dépend de l'entrée doit être prise, le pire chemin est choisi¹. Une fois l'algorithme terminé, nous divisons la complexité calculée par la taille de l'entrée pour obtenir le résultat final.
¹note : Pour être précis, le pire chemin qui est théoriquement possible . Si vous disposez d'un vecteur qui double dynamiquement sa taille chaque fois que sa capacité est épuisée, "le pire des cas" ne signifie pas qu'il faille supposer qu'il devra doubler à chaque fois que la capacité sera épuisée. chaque insertion parce que les insertions sont traitées comme une séquence. Nous sommes autorisés à (et en fait nous devons) utiliser les données connues de état pour éliminer mathématiquement le plus grand nombre possible de cas "encore plus mauvais", même si l'entrée reste inconnue.
La différence essentielle entre l'analyse asymptotique et l'analyse amortie est que la première dépend de l'entrée elle-même, tandis que la seconde dépend de la séquence d'opérations que l'algorithme exécutera.
Par conséquent :
La meilleure référence que j'ai trouvée jusqu'ici pour comprendre l'analyse amortie des algorithmes est le livre suivant Introduction aux algorithmes troisième édition, chapitre 17 : "Analyse amortie". Tout y est, expliqué bien mieux que ce que l'on peut trouver dans un post Stack Overflow. Vous trouverez ce livre dans la bibliothèque de toute université digne de ce nom.
L'analyse asymptotique régulière examine les performances d'une opération individuelle de manière asymptotique, en fonction de la taille du problème. La notation O() est ce qui indique une analyse asymptotique.
L'analyse amortie (qui est aussi une analyse asymptotique) porte sur la total la réalisation d'opérations multiples sur un infrastructure de données partagée .
La différence est que l'analyse amortie prouve généralement que le calcul total requis pour M opérations présente une meilleure garantie de performance que M fois le pire cas pour l'opération individuelle.
Par exemple, une opération individuelle sur un arbre d'évasement de taille N peut prendre jusqu'à O(N) temps. Cependant, une séquence de M opérations sur un arbre de taille N est limitée par O( M(1+log N) + N log N ) temps, ce qui est approximativement O(log N) par opération. Cependant, notez qu'une analyse amortie est beaucoup plus stricte qu'une analyse "cas moyen" : elle prouve que toute possibilité La séquence d'opérations satisfait son pire cas asymptotique.
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
