Quelle est la complexité temporelle de l'opération d'ajout d'un élément à la fin d'un tableau de type ArrayList?

La complexité temporelle d'ajouter un élément à la fin d'un tableau de type ArrayList en moyenne est O(1) — temps amorti constant.

Cela se produit parce qu'ArrayList stocke les éléments dans un tableau de taille fixe. Lorsqu'on ajoute un élément, s'il y a de la place dans le tableau, l'élément est simplement placé dans la case suivante.

Cependant, si le tableau est plein, une opération d'extension est effectuée — un nouveau tableau de taille plus grande est créé, et tous les éléments sont copiés dedans. Cette opération prend O(n) temps, où n est le nombre d'éléments.

Exemple:

ArrayList<Integer> list = new ArrayList<>();
list.add(1); // O(1)
list.add(2); // O(1)
// Lorsqu'on atteint la capacité du tableau, une extension est effectuée — O(n)

Ainsi, la complexité moyenne d'ajout est — O(1), mais dans le pire cas — O(n).