ArrayList tipli massivə element əlavə etmə əməliyyatının vaxt mürəkkəbliyi nədir?

ArrayList tipli massivə element əlavə etmənin orta vaxt mürəkkəbliyi O(1) — amortizasiya olunmuş sabit vaxtdır.

Bu, ArrayList-in elementləri sabit ölçülü massivdə saxlaması ilə əlaqədardır. Element əlavə etdiyimiz zaman və massivdə boş yer varsa, element sadəcə növbəti hüceyrəyə yerləşdirilir.

Lakin, əgər massiv doludursa, genişləndirmə əməliyyatı həyata keçirilir — daha böyük ölçülü yeni massiv yaradılır və bütün elementlər ona köçürülür. Bu əməliyyat O(n) vaxt alır, burada n elementlərin sayıdır.

Misal:

ArrayList<Integer> list = new ArrayList<>();
list.add(1); // O(1)
list.add(2); // O(1)
// Massivin tutumu dolduqda, genişləndirmə — O(n)

Beləliklə, əlavə etmənin orta mürəkkəbliyi — O(1), lakin ən pis halda — O(n).