Dinamik ArrayList-in başlanğıcına element əlavə etmə əməliyyatının vaxt mürəkkəbliyi nədir?

Dinamik massivə (məsələn, Java-da ArrayList) başlanğıca element əlavə etmək vaxt mürəkkəbliyi O(n)-dir, burada n massivdəki elementlərin sayı.

Bu, başlanğıca əlavə edərkən mövcud bütün elementlərin sağa doğru bir mövqe dəyişdirməsini tələb etdiyindən baş verir, bu da yeni element üçün yer açır. Elementlərin kopyalanması prosesi xətti vaxt alır.

Nümunə:

ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);

// Başlanğıca əlavə
list.add(0, 0); // bütün elementləri sağa doğru hərəkət etdirir

Beləliklə, sona əlavə etmək adətən daha sürətlidir (amortizasiya olunmuş O(1)), başlanğıca isə — O(n).