Temps amorti constant

Question

Qu'entend-on par "temps amorti constant" lorsqu'on parle de la complexité temporelle d'un algorithme?

Answer 1

temps amorti expliqué en termes simples:

Si vous faites une opération, disons un million de fois, vous ne vous souciez pas vraiment du pire ou du meilleur cas de cette opération - ce qui vous intéresse, c'est combien de temps vous prenez au total lorsque vous répétez l'opération un million fois.

Ainsi, peu importe si l'opération est très lente de temps en temps, à condition que «de temps en temps» soit suffisamment rare pour que la lenteur soit diluée. Le temps essentiellement amorti signifie «temps moyen pris par opération, si vous effectuez de nombreuses opérations». Le temps amorti n'a pas besoin d'être constant. vous pouvez avoir le temps amorti linéaire et logarithmique ou n'importe quoi d'autre. Prenons l'exemple d'une matrice dynamique, à laquelle vous ajoutez de façon répétée de nouveaux éléments. Normalement ajouter un élément prend du temps constant (c'est-à O(1)). Mais chaque fois que le tableau est plein, vous allouez deux fois plus d'espace, copiez vos données dans la nouvelle région et libérez l'ancien espace. En supposant que les affectations et les libérations s'exécutent en temps constant, ce processus d'agrandissement prend O(n) heure où n est la taille actuelle du tableau.

Ainsi, chaque fois que vous agrandissez, vous prenez environ deux fois plus de temps que le dernier agrandissement. Mais vous avez aussi attendu deux fois plus longtemps avant de le faire! Le coût de chaque élargissement peut ainsi être "étalé" entre les insertions. Cela signifie qu'à long terme, le temps total nécessaire pour ajouter m articles au tableau est O(m), et ainsi le temps amorti (c'est-à-dire le temps par insertion) est O(1).

Answer 2

Cela signifie qu'avec le temps, le scénario le plus défavorable prendra par défaut la valeur O (1), ou temps constant. Un exemple courant est le tableau dynamique. Si nous avons déjà alloué de la mémoire pour une nouvelle entrée, l'ajouter sera O (1). Si nous ne l'avons pas attribué, nous le ferons en allouant, disons, deux fois le montant actuel. Cette insertion particulière pas être O (1), mais plutôt quelque chose d'autre. Ce qui est important, c'est que l'algorithme garantisse qu'après une séquence d'opérations les opérations coûteuses seront amorties et rendront ainsi toute l'opération O (1).

Ou en termes plus stricts,

Il existe une constante c, telle que pour chaque séquence d'opérations (également l'une se terminant par une opération coûteuse) de longueur L, le temps n'est pas supérieure à c * L (Merci Rafał Dowgird)

Answer 3

Les explications ci-dessus s'appliquent à l'analyse agrégée, l'idée de prendre «une moyenne» sur plusieurs opérations. Je ne sais pas comment ils s'appliquent à la méthode des banquiers ou aux méthodes des physiciens de l'analyse amortie.

Maintenant. Je ne suis pas exactement sûr de la bonne réponse. Mais cela aurait à voir avec la condition principale des deux méthodes Physicists + Banker:

(Somme du coût d'exploitation amorti)> = (Somme du coût réel des opérations).La principale difficulté à laquelle je fais face est que, étant donné que les coûts d'exploitation amortissables asymptotiques diffèrent du coût asymptotique normal, je ne suis pas sûr de savoir comment évaluer l'importance des coûts amortis.

C'est quand quelqu'un me donne un coût amorti, je sais que ce n'est pas la même chose que le coût normal-asymptotique Quelles conclusions puis-je tirer du coût amorti alors? Comme nous avons le cas de certaines opérations surchargées alors que d'autres opérations sont sous-facturées, une hypothèse pourrait être que l'estimation des coûts amortis des opérations individuelles serait dénuée de sens. Par exemple: Pour un tas de fibonacci, le coût amorti de juste Decreasing-Key à O (1) est insignifiant puisque les coûts sont réduits par "le travail effectué par des opérations antérieures en augmentant le potentiel du tas".

OU

Nous pourrions avoir une autre hypothèse que des motifs sur les coûts amortis-comme suit:

1. Je sais que l'opération coûteuse va précédée de plusieurs opérations à faible coût. Pour les besoins de l'analyse, je vais surcharger certaines opérations à faible coût, TELLE QUE LE COÛT ASYMPTOTIQUE NE CHANGE PAS. Avec ces opérations à faible coût accru, je peux prouver que l'opération coûteuse a un coût ASYMPTOTIC plus petit.

2. Ainsi, j'ai amélioré/diminué le ASYMPTOTIC-BOUND du coût de n opérations.

Ainsi, l'analyse du coût amorti + les coûts amortis ne sont désormais applicables qu'aux opérations coûteuses. Les opérations bon marché ont le même coût asymptotique amorti que leur coût asymptotique normal.

Answer 4

Je trouve ci-dessous explication Wikipédia utile, après une nouvelle lecture 3 fois:

Source: https://en.wikipedia.org/wiki/Amortized_analysis#Dynamic_Array

« Dynamic Array

Amorti Analyse de l'opération Push pour un tableau dynamique

Considérons un tableau dynamique dont la taille augmente au fur et à mesure que d'autres éléments lui sont ajoutés comme une ArrayList en Java. commencé avec un tableau dynamique de taille 4, il faudrait un temps constant pour pousser quatre éléments sur elle. Cependant, le fait de pousser un cinquième élément sur ce tableau prendrait plus de temps car le tableau devrait créer un nouveau tableau de taille double (8), copier les anciens éléments sur le nouveau tableau, puis ajouter le nouvel élément . Les trois opérations de poussée suivantes prendraient également le temps constant, puis l'ajout suivant nécessiterait un autre doubler lentement la taille de la matrice.

En général, si l'on considère un nombre arbitraire de pousse n à un tableau de taille n, on constate que les opérations de poussée prennent du temps constant, sauf pour le dernier qui prend O (n) pour effectuer la taille doubler opération. Comme il y avait n opérations total, nous pouvons prendre la moyenne de cette situation et constater que pour pousser les éléments sur le tableau dynamique prend: O (n/n) = O (1), constante de temps «

Pour. je crois comprendre une histoire simple:

Supposons que vous avez beaucoup d'argent et, vous voulez les empiler dans une salle et, vous avez les mains et les jambes longues, autant que vous avez besoin maintenant ou.. à l'avenir. Et , vous devez remplir tous dans une seule pièce, il est donc facile de le verrouiller.

Donc, vous allez directement à la fin/coin de la pièce et commencez à les empiler. Au fur et à mesure que vous les empilez, la pièce manquera de place. Cependant, comme vous remplissez, il était facile de les empiler. J'ai l'argent, mets l'argent. Facile. C'est O (1). Nous n'avons pas besoin de déplacer de l'argent précédent.

Une fois que la chambre à court d'espace. Nous avons besoin d'une autre pièce, qui est plus grande. Ici, il y a un problème, puisque nous ne pouvons avoir qu'une seule pièce pour que nous puissions avoir seulement une serrure, nous devons déplacer tout l'argent existant dans cette pièce dans la nouvelle pièce plus grande. Alors, déplacez tout l'argent, de la petite pièce, à la plus grande pièce. C'est-à-dire, empilez-les tous à nouveau. Donc, nous devons déplacer tout l'argent précédent. Donc, c'est O (N). (En supposant que N est le compte total de l'argent précédent)

En d'autres termes, il était facile jusqu'à N, seulement 1 opération, mais quand nous avons besoin de déménager dans une pièce plus grande, nous avons fait N opérations. Donc, en d'autres termes, si nous faisons la moyenne, c'est 1 insertion au début, et 1 déplacement de plus en se déplaçant dans une autre pièce. Total de 2 opérations, une insertion, un déplacement. En supposant que N est gros comme 1 million même dans la petite pièce, les 2 opérations comparées à N (1 million) ne sont pas vraiment un nombre comparable, donc on le considère constant ou O (1).

En supposant quand nous faisons tout ce qui précède dans une autre grande salle, et encore besoin de se déplacer. C'est toujours la même chose. dire, N2 (disons, 1 milliard) est nouveau montant de comptage d'argent dans la plus grande salle

Donc, nous avons N2 (qui comprend N précédent puisque nous allons tous de la petite à plus grande salle)

Nous avons toujours besoin de seulement 2 opérations, l'une est insérée dans une pièce plus grande, puis une autre opération de déplacement pour aller dans une pièce encore plus grande.

Ainsi, même pour N2 (1 milliard), il est de 2 opérations pour chacun. ce qui n'est plus rien. Ainsi, il est constant, ou O (1)

Ainsi, comme les N augmente de N à N2, ou un autre, il n'a pas grande importance. Il est toujours constant, ou O (1) opérations requises pour chacun des N.

---

Supposons maintenant, vous avez N comme 1, très faible, le nombre d'argent est petit, et vous avez une très petite chambre, qui s'adaptera seulement 1 nombre d'argent.

Dès que vous remplissez l'argent dans la salle, la salle est remplie.

Lorsque vous allez dans la plus grande pièce, supposons qu'il ne peut contenir qu'un seul argent de plus, soit un total de 2 points. Cela signifie que le précédent a déplacé de l'argent et 1 de plus. Et encore, c'est rempli. De cette façon, le N augmente lentement, et il n'est plus constant O (1), puisque nous déplaçons tout l'argent de la pièce précédente, mais que nous ne pouvons gagner que 1 argent de plus.

Après 100 fois, la nouvelle chambre correspond à 100 comptes d'argent de l'année précédente et 1 autre argent qu'elle peut accueillir. C'est O (N), puisque O (N + 1) est O (N), c'est-à-dire que le degré de 100 ou 101 est le même, les deux sont des centaines, par opposition à l'histoire précédente . Donc, c'est une manière inefficace d'allouer des pièces (ou de la mémoire/RAM) pour notre argent (variables).

---

Ainsi, un bon moyen est Allouer plus d'chambre, avec des puissances de 2.

1ère chambre size = 1 correspond à nombre d'argent
2ème chambre size = 4 s'intègre nombre d'argent
3ème chambre size = correspond à 8 le nombre d'argent
4ème chambre size = correspond à 16 le nombre d'argent
5ème chambre size = 32 s'intègre nombre d'argent
6e chambre size = 64 s'intègre nombre d'argent
chambre 7 size = correspond à 128 le nombre d'argent
8ème chambre size = correspond à 256 le nombre d'argent
9 chambre size = s'intègre 512 le nombre d'argent
chambre 10 size = correspond à 1024 le nombre d'argent
chambre 11 size = convient à 2.048 le nombre de argent
...
16 taille de la pièce = correspond à 65536 le nombre d'argent ...

chambre 32ème size = 4294967296 s'intègre nombre d'argent ...

chambre 64e size = s'intègre 18.446.744.073.709.551.616 nombre d'argent

Pourquoi est-ce mieux? Parce qu'il semble se développer lentement au début, et plus vite plus tard, c'est-à-dire, par rapport à la quantité de mémoire dans notre RAM. Ceci est utile parce que, dans le premier cas, bien que ce soit bon, la quantité totale de travail à effectuer par argent est fixe (2) et non comparable à la taille de la pièce (N), la pièce que nous avons prise dans la première les étapes peuvent être trop importantes (1 million) que nous n'utiliserons pas complètement si nous pouvons obtenir autant d'argent pour économiser dans le premier cas.

Cependant, dans le dernier cas, les puissances de 2, il se développe dans les limites de notre RAM. Et donc, en augmentant en puissances de 2, les deux l'analyse Armotized reste constante et il est amical pour la RAM limitée que nous avons à ce jour.

Answer 5

Pour développer une manière intuitive de penser à ce sujet, envisager l'insertion d'éléments dans dynamic array (par exemple std::vector en C++).Nous allons tracer un graphique, qui montre la dépendance du nombre d'opérations (Y) nécessaires pour insérer N éléments dans la matrice:

parties verticales du graphique noir correspond à la réaffectation de mémoire afin d'élargir un tableau. Ici, nous pouvons voir que cette dépendance peut être grossièrement représentée comme une ligne. Et cette équation de ligne est Y=C*N + b (C est constante, b = 0 dans notre cas). Par conséquent, nous pouvons dire que nous devons dépenser C*N opérations en moyenne pour ajouter N éléments au tableau, ou C*1 opérations pour ajouter un élément (temps constant amorti).