Complexité amortie en termes simples ?

Question

Quelqu'un peut-il expliquer la complexité amortie en termes simples ? J'ai eu du mal à trouver une définition précise en ligne et je ne sais pas quel est le rapport avec l'analyse des algorithmes. Toute information utile, même si elle est référencée à l'extérieur, serait très appréciée.

Answer 1

La complexité amortie est la dépense totale par opération, évaluée sur une séquence d'opérations.

L'idée est de garantir le coût total de l'ensemble de la séquence, tout en permettant aux opérations individuelles d'être beaucoup plus coûteuses que le coût amorti.

Ejemplo:
Le comportement de C++ std::vector<> . En push_back() augmente la taille du vecteur au-delà de sa valeur pré-allouée, il double la longueur allouée.

Ainsi, un seul push_back() peut prendre O(N) temps d'exécution (car le contenu du tableau est copié dans la nouvelle allocation de mémoire).

Cependant, comme la taille de l'allocation a été doublée, le prochain N-1 appelle à push_back() prendront chacun O(1) le temps de l'exécution. Ainsi, le total des N Les opérations se dérouleront toujours dans le cadre de l O(N) temps, ce qui permet de donner push_back() un coût amorti de O(1) par opération.

---

Sauf indication contraire, la complexité amortie est une garantie asymptotique dans le pire des cas pour toute séquence d'opérations. Cela signifie que

• Tout comme pour la complexité non amortie, la notation en grand O utilisée pour la complexité amortie ignore à la fois les frais généraux initiaux fixes et les facteurs de performance constants. Ainsi, pour évaluer les performances amorties en big-O, vous pouvez généralement supposer que toute séquence d'opérations amorties sera "suffisamment longue" pour amortir une dépense de démarrage fixe. Plus précisément, pour le std::vector<> Par exemple, c'est la raison pour laquelle vous n'avez pas besoin de vous inquiéter de savoir si vous rencontrerez réellement des N des opérations supplémentaires : la nature asymptotique de l'analyse suppose déjà que vous le ferez.

• Outre la longueur arbitraire, l'analyse amortie ne fait pas d'hypothèses sur la séquence d'opérations dont vous mesurez le coût - il s'agit d'une garantie dans le pire des cas pour les opérations suivantes toute séquence possible des opérations. Quelle que soit la qualité du choix des opérations (par exemple, par un adversaire malveillant !), une analyse amortie doit garantir qu'une séquence d'opérations suffisamment longue ne peut pas coûter systématiquement plus que la somme de leurs coûts amortis. C'est pourquoi (à moins qu'ils ne soient spécifiquement mentionnés comme qualificatifs) la "probabilité" et le "cas moyen" ne sont pas pertinents pour l'analyse amortie - pas plus qu'ils ne le sont pour une analyse big-O ordinaire dans le pire des cas !

Answer 2

Dans une analyse amortie, le temps nécessaire à l'exécution d'une séquence d'opérations sur la structure des données est calculé en moyenne sur toutes les opérations effectuées... L'analyse amortie diffère de l'analyse du cas moyen dans la mesure où la probabilité n'intervient pas ; une analyse amortie garantit la performance moyenne de chaque opération dans le cas le plus défavorable.

(extrait de Cormen et al., "Introduction to Algorithms")

Cela peut prêter à confusion, car il est dit à la fois que la durée est calculée en moyenne et qu'il ne s'agit pas d'une analyse de cas moyen. Permettez-moi donc d'essayer d'expliquer cela à l'aide d'une analogie financière (en effet, le mot "amorti" est le plus souvent associé à la banque et à la comptabilité).

Supposons que vous exploitiez une loterie. (Il ne s'agit pas d'acheter un billet de loterie, ce dont nous parlerons dans un instant, mais de gérer la loterie elle-même). Vous imprimez 100 000 billets, que vous vendez au prix d'une unité monétaire chacun. Un de ces billets donne droit à 40 000 unités monétaires.

En supposant que vous parveniez à vendre tous les billets, vous pourriez gagner 60 000 unités monétaires : 100 000 unités monétaires de ventes, moins le prix de 40 000 unités monétaires. Pour vous, la valeur de chaque billet est de 0,60 unité monétaire, amortie sur l'ensemble des billets. Il s'agit d'une valeur fiable, sur laquelle vous pouvez compter. Si vous vous lassez de vendre les billets vous-même et que quelqu'un vient vous proposer de les vendre pour 0,30 unité monétaire chacun, vous savez exactement à quoi vous en tenir.

Pour l'acheteur de la loterie, la situation est différente. L'acheteur a une perte attendue de 0,60 unité monétaire lorsqu'il achète un billet de loterie. Mais il s'agit d'une probabilité : l'acheteur peut acheter dix billets de loterie par jour pendant 30 ans (un peu plus de 100 000 billets) sans jamais gagner. Il peut aussi acheter spontanément un seul billet un jour et gagner 39 999 unités monétaires.

Appliqué à l'analyse de la structure de données, nous parlons du premier cas, où nous amortissons le coût d'une opération de la structure de données (par exemple, l'insertion) sur toutes les opérations de ce type. L'analyse du cas moyen traite de la valeur attendue d'une opération stochastique (par exemple, la recherche), où nous ne pouvons pas calculer le coût total de toutes les opérations, mais où nous pouvons fournir une analyse probabiliste du coût attendu d'une seule d'entre elles.

On dit souvent que l'analyse amortie s'applique à la situation où une opération à coût élevé est rare, ce qui est souvent le cas. Mais ce n'est pas toujours le cas. Considérons, par exemple, la "file d'attente du banquier", qui est une file d'attente premier entré-premier sorti (FIFO), composée de deux piles. (Il s'agit d'une structure de données fonctionnelle classique ; il est possible de construire des piles LIFO bon marché à partir de nœuds immuables à lien unique, mais les FIFO bon marché ne sont pas si évidents). Les opérations sont mises en œuvre comme suit :

put(x):  Push x on the right-hand stack.
y=get(): If the left-hand stack is empty:
           Pop each element off the right-hand stack and
             push it onto the left-hand stack. This effectively
             reverses the right-hand stack onto the left-hand stack.
         Pop and return the top element of the left-hand stack.

Je prétends maintenant que le coût amorti de put y get es O(1) en supposant que je commence et termine avec une file d'attente vide. L'analyse est simple : J'ai toujours put sur la pile de droite, et get de la pile de gauche. Ainsi, à part le If chaque put est un push et chaque get est un pop qui sont tous deux O(1) . Je ne sais pas combien de fois j'exécuterai l'opération. If Cela dépend du modèle de la clause de put et get mais je sais que chaque élément se déplace exactement une fois de la pile de droite à la pile de gauche. Ainsi, le coût total sur l'ensemble de la séquence de n put et n get est : n push es, n pop et n move où un move est un pop suivi d'un push En d'autres termes, les 2n opérations (n put et n get ) aboutissent à 2n push es et 2n pop s. Ainsi, le coût amorti d'un seul put o get est un push et un pop .

Notez que les files d'attente des banquiers sont appelées ainsi précisément en raison de l'analyse de la complexité amortie (et de l'association du mot "amorti" avec la finance). Les files d'attente de banquier sont la réponse à ce qui était autrefois une question d'entretien courante, bien que je pense qu'elle soit maintenant considérée comme trop connue : Proposez une file d'attente qui réalise les trois opérations suivantes en un temps amorti O(1) :

1) Obtenir et supprimer l'élément le plus ancien de la file d'attente,

2) Mettre un nouvel élément dans la file d'attente,

3) Trouver la valeur de l'élément maximal actuel.

Answer 3

Le principe de la "complexité amortie" est le suivant : bien qu'une chose puisse être assez complexe au moment où elle est réalisée, elle est considérée comme "non complexe" puisqu'elle n'est pas réalisée très souvent. Par exemple, si vous créez un arbre binaire qui doit être équilibré de temps en temps - disons une fois tous les 2^n insertions - car bien que l'équilibrage de l'arbre soit assez complexe, il ne se produit qu'une fois toutes les n insertions (par exemple, une fois à l'insertion numéro 256, puis à la 512e, à la 1024e, etc.) Pour toutes les autres insertions, la complexité est O(1) - oui, il faut O(n) une fois toutes les n insertions, mais c'est seulement O(1). 1/n Nous multiplions donc O(n) par 1/n et obtenons O(1). Il s'agit donc d'une "complexité amortie de O(1)", car au fur et à mesure que l'on ajoute des éléments, le temps nécessaire pour rééquilibrer l'arbre est minime.

Answer 4

Amortie signifie divisée sur des cycles répétés. Il est garanti que le comportement le plus défavorable ne se produira pas très souvent. Par exemple, si le cas le plus lent est O(N), mais que la probabilité que cela se produise est seulement O(1/N), et que par ailleurs le processus est O(1), alors l'algorithme aura toujours amorti un temps constant O(1). Il suffit de considérer que le travail de chaque exécution O(N) est réparti entre les N autres exécutions.

Le concept dépend du fait qu'il y ait suffisamment de courses pour diviser le temps total. Si l'algorithme n'est exécuté qu'une seule fois ou s'il doit respecter un délai à chaque exécution, la complexité la plus défavorable est plus pertinente.

Answer 5

Supposons que vous essayez de trouver le kème plus petit élément d'un tableau non trié. Trier le tableau serait O(n logn). Trouver le kème plus petit nombre revient donc à localiser l'index, soit O(1).

Le tableau étant déjà trié, il n'est pas nécessaire de le trier à nouveau. Nous ne rencontrerons jamais le pire scénario plus d'une fois.

Si nous effectuons n requêtes pour essayer de localiser le kième plus petit, le temps sera toujours O(n logn) parce qu'il domine O(1). Si nous calculons la moyenne du temps de chaque opération, ce sera O(n logn) :

(n logn)/n ou O(logn). Donc, complexité temporelle/nombre d'opérations.

Il s'agit d'une complexité amortie.

Je pense que c'est comme ça que ça se passe, je suis en train de l'apprendre aussi