Kokia yra laiko sudėtingumas pridėti elementą į ArrayList tipo masyvą?

ArrayList tipo masyvo pabaigos pridėjimo elemento laiko sudėtingumas vidutiniškai yra O(1) — amortizuotas pastovus laikas.

Tai vyksta todėl, kad ArrayList saugo elementus fiksuoto dydžio masyve. Kai pridedame elementą ir masyve yra laisvos vietos, elementas paprasčiausiai įdedamas į kitą langelį.

Tačiau, jei masyvas yra pilnas, atliekama plėtros operacija — sukuriamas naujas didesnis masyvas ir visi elementai perkopijuojami į jį. Ši operacija užtrunka O(n) laiko, kur n yra elementų skaičius.

Pavyzdys:

ArrayList<Integer> list = new ArrayList<>();
list.add(1); // O(1)
list.add(2); // O(1)
// Kai pasiekiama masyvo talpa, vyksta plėtimas — O(n)

Taigi, vidutinė pridėjimo sudėtingumas — O(1), bet blogiausiu atveju — O(n).