Dinamik massivga element qo'shish operatsiyasining vaqt murakkabligi qanday?

Dinamik massivga element qo'shish odatda O(1) amortizatsiya vaqt murakkabligiga ega.

Tushuntirish:

• Agar massivda bo'sh joy bo'lsa, element konstant vaqt ichida qo'shiladi.
• Agar joy bo'lmasa, massiv yangi, kattaroq xotira blokini ajratadi (odatda ikki baravar ko'paytiradi), eski elementlarni ko'chiradi va yangi elementni qo'shadi.

Garchi kengaytirish operatsiyasi O(n) vaqt oladigan bo'lsa-da, u kamdan-kam hollarda yuzaga keladi, shuning uchun qo'shishning o'rtacha (amortizatsiya qilingan) murakkabligi O(1) qoladi.

Go tilida slices bilan misol:

var arr []int
arr = append(arr, 10) // element qo'shish

append kerak bo'lsa, slice avtomatik ravishda kengayadi.