Qu'entend-on par "temps constant amorti" lorsqu'on parle de la complexité temporelle d'un algorithme ?
Le temps amorti expliqué en termes simples :
Si vous effectuez 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 le temps pris au total lorsque vous répétez l'opération un million de fois.
Il importe donc peu que l'opération soit très lente une fois de temps en temps, tant que cette "fois de temps en temps" est suffisamment rare pour que la lenteur soit diluée. Essentiellement, le temps amorti signifie "le temps moyen pris par opération, si vous effectuez de nombreuses opérations". Le temps amorti ne doit pas nécessairement être constant ; vous pouvez avoir un temps amorti linéaire et logarithmique ou autre.
Prenons l'exemple de Mats, qui parle d'un tableau dynamique, auquel vous ajoutez régulièrement de nouveaux éléments. Normalement, l'ajout d'un élément prend un temps constant (c'est-à-dire, 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 allocations et les libérations se déroulent en temps constant, ce processus d'agrandissement prend O(n) temps où n est la taille actuelle du tableau.
Ainsi, à chaque élargissement, vous prenez environ deux fois plus de temps que lors du dernier élargissement. Mais vous avez également attendu deux fois plus longtemps avant de le faire ! Le coût de chaque élargissement peut donc être "réparti" entre les insertions. Cela signifie qu'à long terme, le temps total consacré à l'ajout d'un nouveau membre de la famille est de l'ordre de 2 à 3 ans. m dans le tableau est O(m) et le temps amorti (c'est-à-dire le temps par insertion) est donc le suivant O(1) .
Juste une remarque en termes de notation : Un temps d'exécution constant amorti de O(n) est souvent écrit O(n)+, au lieu de O(n). L'ajout du signe plus indique que ce temps d'exécution n'est pas garanti pour être O(n) et peut en fait dépasser ce temps d'exécution.
Dans votre interprétation de l'exemple de Mats, vous supposez un temps constant par article pour l'allocation, la copie et la libération. Par conséquent, la durée d'exécution sera constante, quelle que soit la manière dont les processus d'agrandissement sont répartis. Il n'y a jamais d'opération dont la durée d'exécution croît plus vite que O(1) par point de cette réponse.
Cela signifie qu'au fil du temps, le scénario le plus défavorable deviendra O(1), soit un 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 encore allouée, nous le ferons en allouant, disons, le double de la quantité actuelle. Cette insertion particulière sera no être O(1), mais plutôt quelque chose d'autre.
Ce qui est important, c'est que l'algorithme garantit qu'après une séquence d'opérations, les opérations coûteuses seront amorties, ce qui rendra l'opération entière O(1).
Ou en termes plus stricts,
Il existe une constante c, telle que pour chaque séquence d'opérations (même celle se terminant par une opération coûteuse) de longueur L, le temps n'est pas supérieur à c*L (Merci Rafał Dowgird )
"après un nombre suffisamment important d'opérations" - le temps amorti constant ne nécessite pas cette condition. Il existe une constante c, telle que pour tous séquence d'opérations (y compris celle se terminant par une opération coûteuse) de longueur L, le temps n'est pas supérieur à c*L.
Où se trouve cette en allouant le double du montant d'où vient-il ? Ne devrions-nous pas allouer des fonds pour une entrée ? Ou s'agit-il d'un exemple hypothétique ?
@talekeDskobaDa Il ne s'agit pas d'un exemple arbitraire, mais d'un algorithme largement utilisé. Si nous allouons de l'espace pour une entrée à la fois comme vous le suggérez, le temps amorti pour l'insertion d'une seule valeur serait O(n). Si nous doublons l'espace lorsqu'il est plein, le temps amorti est bien meilleur, O(1). Pour être clair, le problème de l'allocation d'espace pour un élément à la fois est qu'un tableau a besoin d'un grand bloc d'espace continu. Il est facile d'obtenir un bloc plus grand auprès du système d'exploitation, mais il est souvent impossible d'étendre un bloc existant parce qu'il peut y avoir d'autres données stockées directement après lui.
Pour développer une façon intuitive d'y penser, considérons l'insertion d'éléments dans tableau dynamique (par exemple std::vector en C++). Traçons un graphique qui montre la dépendance du nombre d'opérations (Y) nécessaires pour insérer N éléments dans un tableau :
Les parties verticales du graphique noir correspondent à des réallocations de mémoire afin d'étendre un tableau. Ici, nous pouvons voir que cette dépendance peut être grossièrement représentée par une ligne. Et l'équation de cette ligne est Y=C*N + b ( C est constante, b = 0 dans notre cas). Nous pouvons donc dire que nous devons dépenser C*N opérations en moyenne pour ajouter N éléments au tableau, ou C*1 pour ajouter un élément (amorti en temps constant).
J'ai trouvé l'explication de Wikipedia ci-dessous utile, après l'avoir lue trois fois :
Source : https://en.wikipedia.org/wiki/Amortized_analysis#Dynamic_Array
"Tableau dynamique
Analyse amortie de l'opération de poussée pour un réseau dynamique
Considérons un tableau dynamique dont la taille augmente au fur et à mesure que le nombre d'éléments augmente. tel qu'un ArrayList en Java. Si nous commençons avec un tableau dynamique de taille 4, il faudrait un temps constant pour y ajouter quatre éléments. Cependant, l'ajout d'un cinquième élément à ce tableau prendrait plus de temps, car le tableau tableau devrait créer un nouveau tableau de taille double (8), copier les anciens éléments dans le nouveau tableau, puis ajouter le nouvel élément. élément. Les trois opérations "push" suivantes prendraient également des temps constants de temps constant, et l'ajout suivant nécessiterait un autre doublement lent de la taille du tableau. lent doublement de la taille du tableau.
En général, si l'on considère un nombre arbitraire de poussées n sur un tableau de taille n, nous remarquons que les opérations de poussée prennent un temps constant sauf la dernière qui prend O(n) temps pour effectuer l'opération de doublement de la taille. de la taille. Puisqu'il y a eu n opérations au total, nous pouvons prendre la moyenne et trouver que pour pousser des éléments dans le tableau dynamique prend : O(n/n)=O(1), temps constant".
Selon moi, il s'agit d'une simple histoire :
Supposons que vous ayez beaucoup d'argent. Vous voulez les empiler dans une pièce. Vous avez de longues mains et de longues jambes, aussi longues que vous en avez besoin aujourd'hui ou à l'avenir. Et vous devez tout remplir dans une pièce, pour qu'il soit facile de la fermer à clé.
Vous allez donc jusqu'au bout/au coin de la pièce et vous commencez à les empiler. Au fur et à mesure que vous les empilez, la pièce va lentement manquer d'espace. Cependant, au fur et à mesure que vous la remplissez, il est facile de l'empiler. Vous avez l'argent, vous mettez l'argent. C'est facile. C'est O(1). Nous n'avons pas besoin de déplacer l'argent précédent.
Une fois que la salle manque d'espace. Nous avons besoin d'une autre pièce, plus grande. Ici, il y a un problème, puisque nous ne pouvons avoir qu'une seule pièce et donc qu'une seule serrure, nous devons transférer tout l'argent existant dans cette pièce dans la nouvelle pièce plus grande. Il faut donc déplacer tout l'argent de la petite pièce vers la plus grande. En d'autres termes, il faut les empiler à nouveau. Nous devons donc déplacer tout l'argent précédent. C'est donc 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 lorsque nous avons dû déménager dans une pièce plus grande, nous avons effectué N opérations. En d'autres termes, si nous faisons la moyenne, il s'agit d'une insertion au début, et d'un déplacement supplémentaire lors du déménagement dans une autre pièce. Soit un total de 2 opérations, une insertion et un déplacement.
En supposant que N est grand comme 1 million, même dans une petite pièce, les 2 opérations par rapport à N (1 million) ne sont pas vraiment un nombre comparable, et sont donc considérées comme constantes ou O(1).
En supposant que nous fassions tout cela dans une autre pièce plus grande et que nous devions à nouveau déménager. C'est toujours la même chose. disons, N2 (disons, 1 milliard) est le nouveau montant du compte d'argent dans la pièce plus grande
Nous avons donc N2 (qui inclut N de la pièce précédente, puisque nous déplaçons toutes les pièces de la petite à la grande).
Nous n'avons besoin que de deux opérations, l'une étant l'insertion dans une pièce plus grande, puis une autre opération de déplacement vers une pièce encore plus grande.
Ainsi, même pour 2 N (1 milliard), il s'agit de 2 opérations pour chacun, ce qui n'est encore rien. C'est donc constant, ou O(1).
Ainsi, lorsque le N passe de N à N2, ou autre, cela n'a pas beaucoup d'importance. Il reste constant, soit O(1) opérations nécessaires pour chacun des N .
Supposons maintenant que vous ayez N égal à 1, très petit, que le nombre d'argent soit petit et que vous disposiez d'une pièce très petite, qui ne peut contenir qu'un seul nombre d'argent.
Dès que vous remplissez l'argent dans la pièce, la pièce est remplie.
Lorsque vous allez dans la pièce la plus grande, supposez qu'elle ne peut contenir qu'une seule somme d'argent supplémentaire, soit un total de 2 pièces d'argent. C'est-à-dire l'argent déplacé précédemment et un autre. Et la pièce est à nouveau remplie.
De cette façon, le N augmente lentement et 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 y mettre qu'un seul argent supplémentaire.
Après 100 fois, la nouvelle pièce contient 100 comptes d'argent de la précédente et 1 compte d'argent supplémentaire 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 de un à des millions et de un à des milliards.
Il s'agit donc d'une manière inefficace d'allouer des pièces (ou de la mémoire/de la RAM) pour notre argent (variables).
Une bonne façon de procéder est donc d'allouer plus d'espace, avec des puissances de 2.
1ère taille de pièce = 1 pièce d'argent
2ème taille de pièce = 4 pièces d'argent
3ème taille de pièce = 8 pièces d'argent
Taille de la 4ème pièce = 16 pièces d'argent
Taille de la 5ème pièce = permet de contenir 32 pièces d'argent
Taille de la 6e pièce = 64 pièces d'argent
Taille de la 7e pièce = 128 pièces d'argent
Taille de la 8e pièce = 256 pièces d'argent
Taille de la 9e pièce = correspond à 512 pièces d'argent
Taille de la 10e pièce = correspond à 1024 pièces d'argent
Taille de la 11e pièce = 2 048 pièces d'argent
...
Taille de la 16ème pièce = 65 536 pièces d'argent
...
32ème taille de pièce = correspond à 4 294 967 296 pièces d'argent
...
64ème taille de pièce= correspond à 18,446,744,073,709,551,616 compte d'argent
Pourquoi est-ce mieux ? Parce qu'il semble croître lentement au début, et plus rapidement par la suite, c'est-à-dire par rapport à la quantité de mémoire dans notre RAM.
Cela est utile car, dans le premier cas, même si c'est une bonne chose, le montant total du travail à effectuer par argent est fixe (2) et n'est pas comparable à la taille de la pièce (N), la pièce que nous avons prise dans les étapes initiales pourrait être trop grande (1 million) et nous pourrions ne pas l'utiliser pleinement en fonction de la possibilité d'obtenir autant d'argent à économiser dans le premier cas.
Cependant, dans le dernier cas, celui des puissances de 2, il croît dans les limites de notre mémoire vive. Ainsi, en augmentant les puissances de 2, l'analyse armotisée reste constante et est adaptée à la mémoire vive limitée dont nous disposons actuellement.
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.
1 votes
mortoray.com/2014/08/11/qu'est-ce que le temps amorti ?