Wie ist die zeitliche Komplexität der Operation zum Hinzufügen eines Elements zu einem dynamischen Array?

Das Hinzufügen eines Elements zu einem dynamischen Array hat in der Regel eine amortisierte Laufzeitkomplexität von O(1).

Erläuterung:

• Wenn im Array Platz vorhanden ist, wird das Element in konstanter Zeit hinzugefügt.
• Wenn kein Platz mehr ist, reserviert das Array einen neuen größeren Speicherblock (meist doppelt so groß), kopiert die alten Elemente und fügt das Neue hinzu.

Obwohl die Erweiterungsoperation O(n) dauert, tritt sie nicht häufig auf, sodass die durchschnittliche (amortisierte) Komplexität des Hinzufügens bei O(1) bleibt.

Beispiel in Go mit Slices:

var arr []int
arr = append(arr, 10) // Element hinzufügen

append erweitert den Slice automatisch bei Bedarf.