Wie hoch ist die zeitliche Komplexität der Operation, ein Element am Ende eines Arrays mit einem Slice hinzuzufügen?

In Go hat die Operation, ein Element ans Ende eines Slices (append) hinzuzufügen, eine amortisierte Laufzeitkomplexität von O(1).

Erklärung:

• Wenn der Slice genügend Kapazität (capacity) hat, erfolgt das Hinzufügen eines Elements einfach durch Schreiben an den nächsten freien Index — das ist eine Operation in konstanter Zeit.

• Wenn die Kapazität nicht ausreicht, wird ein neues Array mit größerer Größe alloziert, die alten Elemente werden kopiert und das neue Element wird hinzugefügt — diese Operation dauert O(n), wobei n die aktuelle Größe des Slices ist.

Da solche Neuallokationen jedoch nicht bei jeder Hinzufügung, sondern nur periodisch auftreten, bleibt die durchschnittliche (amortisierte) Komplexität des Hinzufügens O(1).