Mekkora az időbeli komplexitású az elem hozzáadása a tömb végéhez szelet segítségével?

Go-ban az elem hozzáadása a slice végéhez (append) amortizált időkomplexitással O(1).

Magyarázat:

• Ha a slice rendelkezik elegendő kapacitással (capacity), az elem hozzáadása egyszerűen a következő szabad indexre írással történik — ez egy konstans időtartamú művelet.

• Ha a kapacitás nem elegendő, akkor egy nagyobb méretű új tömböt allokálunk, a régi elemeket átmásoljuk, és az új elemet hozzáadjuk — ez a művelet O(n) időt vesz igénybe, ahol n a slice aktuális mérete.

Azonban, mivel ilyen újraelosztások nem minden hozzáadáskor történnek, hanem csak időszakosan, az átlagos (amortizált) hozzáadási komplexitás továbbra is O(1).