Wie ist die zeitliche Komplexität beim Hinzufügen eines neuen Elements zum Wörterbuch?

Die zeitliche Komplexität beim Hinzufügen eines neuen Elements zu einem Wörterbuch (z.B. Dictionary in Swift oder NSMutableDictionary in Objective-C) beträgt in der Regel O(1) im Durchschnitt. Dies liegt daran, dass das Wörterbuch auf einer Hashtabelle basiert, bei der die Hash-Berechnung und das Einfügen in konstanter Zeit erfolgen.

Im schlimmsten Fall, bei Kollisionen oder wenn das interne Array erweitert werden muss, kann die Komplexität vorübergehend auf O(n) ansteigen, wobei n die Anzahl der Elemente ist.

Beispiel in Swift:

var dict = [String: Int]()
dict["key"] = 42 // Hinzufügen in O(1) im Durchschnitt