[algorithm] Temps amorti constant


Answers

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 ne sera pas 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 y a une constante c, telle que pour chaque séquence d'opérations (aussi une fin avec une opération coûteuse) de longueur L, le temps n'est pas supérieur à c * L (Merci Rafał Dowgird )

Question

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




J'ai trouvé ci-dessous Wikipedia explication utile, après avoir répété la lecture pour 3 fois:

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

"Dynamic Array

Analyse amortie 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 y sont ajoutés, comme une ArrayList en Java. Si nous commencions avec un tableau dynamique de taille 4, il faudrait un temps constant pour y insérer quatre éléments. Cependant, 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 de la même manière un temps constant, puis l'addition suivante nécessiterait un autre doublage lent de la taille du réseau.

En général, si nous considérons un nombre arbitraire de poussées n dans un tableau de taille n, nous remarquons que les opérations push prennent un temps constant, sauf le dernier qui prend le temps O (n) pour effectuer l'opération de doublage de taille. Comme il y avait n opérations totales, nous pouvons prendre la moyenne de ceci et trouver que pour pousser des éléments sur le tableau dynamique prend: O (n / n) = O (1), temps constant. "

À ma compréhension comme une histoire simple:

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

Donc, vous allez à la fin / coin de la pièce et commencez à les empiler. Au fur et à mesure que vous les empilez, la pièce manquera d'espace. 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 la pièce manque 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. Donc, 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 nombre total d'argent de l'argent précédent)

En d'autres termes, c'était facile jusqu'à N, une seule 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 mouvement.

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 pièce plus grande, et encore besoin de bouger. C'est encore le même. disons, N2 (disons, 1 milliard) est une nouvelle quantité de compte d'argent dans la plus grande salle

Donc, nous avons N2 (qui inclut N du précédent puisque nous passons tous de la petite à la grande pièce)

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.

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

Ainsi, lorsque le N augmente de N à N2 ou autre, cela n'a pas beaucoup d'importance. Il est toujours constant, ou O (1) opérations requises pour chacun des N.

Supposons maintenant, vous avez N comme 1, très petit, le compte d'argent est petit, et vous avez une très petite pièce, qui ne correspondra qu'à 1 compte d'argent.

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

Quand 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 d'argent. 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 grandit 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 ne pouvons faire 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 façon inefficace d'allouer des pièces (ou de la mémoire / RAM) pour notre argent (variables).

Donc, un bon moyen est d'allouer plus de place, avec des puissances de 2.

Taille de la 1ère pièce = correspond à 1 compte d'argent
2e taille de la chambre = correspond à 4 comptes d'argent
Taille de la 3ème pièce = correspond à 8 unités d'argent
4e taille de la pièce = correspond à 16 comptes d'argent
5e taille de la pièce = correspond à 32 comptes d'argent
6e chambre = correspond à 64 comptes d'argent
7e taille de la pièce = correspond à 128 chefs d'accusation
Taille de la 8e chambre = correspond à 256 comptes d'argent
Taille de la 9e chambre = correspond à 512 comptes d'argent
10e taille de la pièce = correspond à 1024 unités d'argent
Taille de la 11e chambre = correspond à 2 048 comptes d'argent
...
16e chambre = correspond à 65 536 unités d'argent
...
La taille de la 32e chambre correspond à 4 294 967 296
...
64e chambre = 18 446 744 073 709 551 616 $

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 la quantité totale de travail à faire soit fixe (2) et non comparable à la taille de la pièce (N), la pièce que nous avons prise dans les premières étapes pourrait être trop grand (1 million) que nous ne pouvons pas utiliser complètement selon si nous pouvons obtenir autant d'argent pour économiser du tout dans le premier cas.

Cependant, dans le dernier cas, pouvoirs 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.






Related