Le temps amortie est la façon d’exprimer la complexité temporelle quand un algorithme a la très mauvaise complexité temporelle seulement une fois dans le temps en plus de la complexité temporelle qui se produit la plupart du temps. Un bon exemple serait une ArrayList qui est une structure de données qui contient un tableau et qui peut être étendue. Une autre définition de Stack Overflow est le temps moyen pris par opération, si vous faites beaucoup d’opérations.
Lorsque ArrayList atteint la capacité du tableau en elle, alors elle crée un nouveau tableau avec la taille doublée de l’ancien tableau et copie tous les éléments dans l’ancien tableau vers le nouveau tableau. Dans ArrayList, deux complexités temporelles existent ; l’une est O(1) et l’autre est O(n).
Lorsque le tableau en lui n’a pas atteint sa capacité et a encore assez d’espace pour insérer des éléments
Pour insérer un élément dans le tableau dans ce cas, nous devons juste mettre l’élément après le dernier élément. Nous avons encore de l’espace pour insérer des éléments.
Quand le tableau en lui a atteint sa capacité et doit se recréer avec la taille doublée
Le tableau a atteint sa capacité et nous n’avons plus d’emplacements disponibles. Alors nous devons créer un tout nouveau tableau avec la taille doublée. Et ensuite copier les éléments de l’ancien vers le nouveau, ce qui prend O(n) où n est la capacité de l’ancien tableau et le pire cas.
Pour exprimer ces deux complexités de temps, le temps amorti est ici. Ce qu’il fait est de nous laisser décrire le pire cas se produit une fois de temps en temps chaque fois que le tableau interne a atteint sa capacité.
Mais une fois que cela se produit, cela ne se reproduira pas pendant si longtemps que le coût est « amorti. » (Cracking the Coding Interview 6th edition 43)
Alors comment on décrit les deux complexités?
Dans le cas de l’ArrayList, on peut dire que
L’insertion prend O(n) quand la capacité a été atteinte, et le temps amorti pour chaque insertion est O(1).
Mais soyons précis pour la pire complexité temporelle sans simplifier ce temps. Si la capacité du tableau interne commence par 1, alors les capacités seront de 1, 2, 4, 8, 16… X quand il atteint la capacité et est doublé. Il faut 1, 2, 4, 8 16… X éléments pour copier dans le nouveau tableau en fonction de la capacité qui a été atteinte. Donc la complexité temporelle sera de 1 + 2 + 4 + 8 + 16 +… X. Si vous pensez à partir de X, ce sera X + X/2 + X/4 + X/8… + 1 = 2X approximativement. Donc en d’autres termes précisément,
L’insertion prend O(2X) lorsque la capacité de X a été atteinte, et le temps amorti pour chaque insertion est O(1).
.
