ArrayList türündeki bir dizinin sonuna öğe ekleme işleminin zaman karmaşıklığı nedir?

ArrayList türündeki bir dizinin sonuna öğe eklemenin ortalama zaman karmaşıklığı O(1) — amortize sabit zaman.

Bu, ArrayList'in öğeleri sabit boyutlu bir dizi içinde saklaması nedeniyle olur. Bir öğe eklediğimizde ve dizide boş alan varsa, öğe doğrudan bir sonraki hücreye yerleştirilir.

Ancak, dizi doluysa, genişletme işlemi gerçekleşir — daha büyük bir yeni dizi oluşturulur ve tüm öğeler ona kopyalanır. Bu işlem O(n) zaman alır, burada n öğe sayısıdır.

Örnek:

ArrayList<Integer> list = new ArrayList<>();
list.add(1); // O(1)
list.add(2); // O(1)
// Dizi kapasitesine ulaşıldığında genişletme yapılır — O(n)

Bu nedenle, ekleme işleminin ortalama karmaşıklığı — O(1), ancak en kötü durumda — O(n).