ArrayList ga element qo'shishda vaqt murakkabligi qanday aniqlanadi?

ArrayList ga element qo'shish vaqt murakkabligi odatda amortizatsiya qilingan holda O(1)dir. Bu shundan iboratki:

• Agar ArrayListning ichki massivi bo'sh joyga ega bo'lsa, yangi element oddiygina keyingi pozitsiyaga yoziladi — bu operatsiya doimiy vaqt O(1)ni oladi.
• Agar ichki massiv to'liq bo'lsa, uni kengaytirish amalga oshiriladi: kattaroq o'lchamdagi yangi massiv yaratiladi va barcha elementlar unga ko'chiriladi. Bu operatsiya O(n) vaqt oladi, bu yerda n — ro'yxatning joriy o'lchami.

Ammo, kengaytirish har bir qo'shishda emas, balki vaqti-vaqti bilan amalga oshiriladi, shuning uchun qo'shishning o'rtacha (amortizatsiya qilingan) murakkabligi O(1)da qoladi.

Misol:

ArrayList<Integer> list = new ArrayList<>();
list.add(10); // Amortizatsiya qilingan O(1)