Expliquer le concept de temps amorti à l'aide de ArrayList? En quoi le temps d'insertion de n Array List est-il O (N).

Question

Veuillez expliquer avec un simple problème

Je vais dans un livre où il est dit que ArrayList va doubler après avoir atteint sa limite et si le ArrayList est plein, il prend O (N) le temps d'insertion pour l'insertion de l'élément N .Kindly expliquer en prenant un ArrayList de quelques éléments

Answer 1

temps amorti expliqué en termes simples:

Si vous faites une opération disent un million de fois, vous ne se soucient pas vraiment le pire des cas ou les mieux 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 de 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 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 s'exécutent en temps constant, ce processus d'agrandissement prend l'heure O (n) 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 éléments au tableau est O (m), et donc le temps amorti (c'est-à-dire le temps par insertion) est O (1).