Quelle est la complexité temporelle de l'opération d'ajout d'un élément dans un tableau dynamique?

L'ajout d'un élément à un tableau dynamique a généralement une complexité temporelle amortie de O(1).

Explication:

• Si l'espace est disponible dans le tableau, l'ajout se fait en temps constant.
• Si l'espace n'est pas suffisant, le tableau alloue un nouveau bloc de mémoire plus grand (généralement le double), copie les anciens éléments et ajoute le nouveau.

Bien que l'opération d'extension prenne O(n), elle ne se produit pas fréquemment, donc la complexité moyenne (amortie) de l'ajout reste O(1).

Exemple en Go avec des slices:

var arr []int
arr = append(arr, 10) // ajout d'un élément

append étendra automatiquement le slice si nécessaire.