Quelle est la complexité temporelle de l'ajout d'un nouvel élément dans le dictionnaire?

La complexité temporelle de l'ajout d'un nouvel élément dans un dictionnaire (par exemple, Dictionary en Swift ou NSMutableDictionary en Objective-C) est généralement O(1) en moyenne. Cela est dû au fait que le dictionnaire est implémenté à l'aide d'une table de hachage, où le calcul du hachage et l'insertion se font en temps constant.

Cependant, dans le pire des cas, en cas de collisions ou de nécessité d'agrandir le tableau interne, la complexité peut temporairement augmenter jusqu'à O(n), où n est le nombre d'éléments.

Exemple en Swift:

var dict = [String: Int]()
dict["key"] = 42 // Ajout en O(1) en moyenne