Tableau dynamique
Considérons un tableau dynamique qui se développe dans taille car plus d’éléments y sont ajoutés, tels que ArrayList en Java ou std::vectoren C++. Si nous commencions avec un tableau dynamique de taille 4, nous pourrions y pousser 4 éléments, et chaque opération prendrait un temps constant. Pourtant, 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 de la taille actuelle (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 nouveau doublement lent de la taille du tableau.
En général, si l’on considère un nombre arbitraire de poussées n + 1 vers un tableau de taille n, on remarque que les opérations de poussée prennent un temps constant sauf pour la dernière qui prend Θ(n) {\displaystyle\Theta(n)}
temps pour effectuer l’opération de doublement de taille. Puisqu’il y a eu n + 1 opérations au total, nous pouvons prendre la moyenne de ceci et constater que pousser des éléments sur le tableau dynamique prend: n Θ(1) + Θ(n) n + 1 = Θ(1) {\displaystyle {\tfrac {n\Thêta(1) +\Thêta(n)} {n +1}} = \Thêta(1)}
, temps constant.
QueueEdit
Montré est une implémentation Ruby d’une file d’attente, une structure de données FIFO:
class Queue def initialize @input = @output = end def enqueue(element) @input << element end def dequeue if @output.empty? while @input.any? @output << @input.pop end end @output.pop endend
L’opération de mise en file d’attente pousse simplement un élément sur le tableau d’entrée; cette opération ne dépend pas des longueurs d’entrée ou de sortie et s’exécute donc en temps constant.
Cependant l’opération de mise en file d’attente est plus compliquée. Si le tableau de sortie contient déjà certains éléments, dequeue s’exécute en temps constant; sinon, dequeue prend O(n) {\displaystyle O(n)}
temps pour ajouter tous les éléments sur le tableau de sortie à partir du tableau d’entrée, où n est la longueur actuelle du tableau d’entrée. Après avoir copié n éléments d’entrée, nous pouvons effectuer n opérations de mise en file d’attente, chacune prenant un temps constant, avant que le tableau de sortie ne soit à nouveau vide. Ainsi, nous pouvons effectuer une séquence de n opérations de mise en file d’attente en seulement O(n) {\displaystyle O(n)}
temps, ce qui implique que le temps amorti de chaque opération de mise en file d’attente est O(1) {\displaystyle O(1)}
