Kāda ir laika sarežģītība elementa pievienošanai ArrayList tipa masīvam?

ArrayList tipa masīva elementa pievienošanas laika sarežģītība vidēji ir O(1) — amortizēts konstants laiks.

Tas notiek tāpēc, ka ArrayList glabā elementus fiksēta lieluma masīvā. Kad pievienojam elementu un masīvā ir brīva vieta, elements vienkārši tiek ievietots nākamajā šūnā.

Tomēr, ja masīvs ir pilns, tiek veikta paplašināšanas operācija — tiek izveidots jauns, lielāks masīvs, un visi elementi tiek pārvietoti uz to. Šī operācija aizņem O(n) laiku, kur n ir elementu skaits.

Piemērs:

ArrayList<Integer> list = new ArrayList<>();
list.add(1); // O(1)
list.add(2); // O(1)
// Kad sasniegta masīva ietilpība, notiek paplašināšana — O(n)

Tādējādi, vidējā pievienošanas sarežģītība ir — O(1), bet sliktākajā gadījumā — O(n).