Mekkora az időbeli komplexitása annak az műveletnek, amikor egy elemet hozzáadunk egy dinamikus tömbhöz?

Dinamikus tömbhöz elem hozzáadása általában O(1) amortizált időkomplexitással jár.

Magyarázat:

• Ha van szabad hely a tömbben, az elem hozzáadása konstans időt vesz igénybe.
• Ha nincs hely, a tömb egy nagyobb memória blokkot foglal (általában kétszeres méretűt), átmásolja a régi elemeket és hozzáadja az újat.

Bár a bővítési művelet O(n) időt vesz igénybe, nem fordul elő gyakran, így az átlagos (amortizált) komplexitás O(1) marad.

Go nyelven szeletekkel például:

var arr []int
arr = append(arr, 10) // elem hozzáadása

Az append automatikusan bővíti a szeletet szükség esetén.