ArrayList turidagi massivning oxiriga element qo'shish operatsiyasining vaqt murakkabligi qanday?

ArrayList turidagi massivga element qo'shishning o'rtacha vaqt murakkabligi O(1) — amortizatsiya qilingan doimiy vaqt.

Bu shundan iboratki, ArrayList elementlarni doimiy o'lchamdagi massivda saqlaydi. Element qo'shganda va massivda bo'sh joy bo'lsa, element oddiygina keyingi katakka joylashtiriladi.

Ammo, agar massiv to'liq bo'lsa, kengaytirish operatsiyasi amalga oshiriladi — yangi, kattaroq massiv yaratiladi va barcha elementlar unga ko'chiriladi. Bu operatsiya O(n) vaqt oladi, bu yerda n elementlar soni.

Misol:

ArrayList<Integer> list = new ArrayList<>();
list.add(1); // O(1)
list.add(2); // O(1)
// Massivning sig'imi to'ldirilganda, kengaytirish amalga oshiriladi — O(n)

Shunday qilib, qo'shishning o'rtacha murakkabligi — O(1), lekin eng yomon holatda — O(n).