Amortized Analysis, bir algoritmanın performansını analiz etmek için kullanılan bir tekniktir. Bu, bir dizi operasyonun maliyetini hesaplarken, operasyonlar arasında maliyetin dağıtılabileceği durumları dikkate alır.

Dinamik dizi senaryosunda, bir eleman eklemek genellikle O(1) zaman alır - bu, sabit zaman karmaşıklığı anlamına gelir. Ancak, dizi dolu olduğunda ve yeni bir eleman eklememiz gerektiğinde, diziyi genişletmek ve tüm elemanları yeni diziye kopyalamak O(n) zaman alır. Bu, lineer zaman karmaşıklığı anlamına gelir ve çok daha yavaştır.

Bununla birlikte, her eleman ekleme işlemi bu yeniden boyutlandırma işlemini tetiklemez. Diziyi her seferinde iki katına çıkarırsak, n eleman eklediğimizde sadece log(n) kez yeniden boyutlandırma yaparız. Diğer tüm ekleme işlemleri hala O(1) zaman alır.

Bu nedenle, amortize zaman karmaşıklığı hesaplama, tüm ekleme işlemlerinin maliyetini toplar ve bunları n sayısına böler. Bu, her ekleme işleminin ortalama maliyetini verir.

Sonuç olarak, dinamik bir dizinin amortize zaman karmaşıklığı O(1)'dir. Bu, her ekleme işleminin "ortalama" maliyetinin sabit olduğu anlamına gelir, çünkü yüksek maliyetli yeniden boyutlandırma işlemlerinin maliyeti, düşük maliyetli normal ekleme işlemleri arasında dağıtılır.

Bu, genellikle amortize analizin en yaygın kullanıldığı yerdir, ancak diğer algoritmalar ve veri yapıları için de kullanılabilir. Amortize analiz, algoritmanın "tipik" davranışını anlamak için çok yararlıdır, çünkü nadir durumların maliyeti genellikle daha sık karşılaşılan durumlar arasında dağıtılır.

"Geometric Increase in Capacity" kavramı, dinamik dizi yapısında kullanılan bir büyütme stratejisini ifade eder. Bu stratejiye göre, bir dizi kapasitesini aştığında, dizinin yeni kapasitesi genellikle eski kapasitenin bir katsayısı (genellikle 2) ile artırılır. Yani, dizi kapasitesi geometrik bir dizi (örneğin, 1, 2, 4, 8, 16, ...) takip eder.

Bu tür bir strateji kullanmanın avantajı, dizinin boyutunun büyüdükçe, boyutunu artırmak için gereken yeniden boyutlandırma işlemlerinin sayısının azalmasıdır. Bu, büyük dizilerle çalışırken zaman karmaşıklığını düşürür. Bu, genellikle, yeni elemanlar eklendikçe, dizinin yeniden boyutlandırılmasının daha az sıklıkta gerektiği anlamına gelir.

Aşağıdaki Python kodu, bir dizi kapasitesini aştığında kapasitenin geometrik olarak nasıl arttığını gösterir:

class DynamicArray:
    def __init__(self):
        self.data = [None]
        self.n = 0  # number of elements

    def append(self, value):
        if self.n == len(self.data):  # if capacity is reached, resize
            self.resize(2 * len(self.data))  # double the size
        self.data[self.n] = value
        self.n += 1

    def resize(self, capacity):
        temp = [None] * capacity
        for i in range(self.n):
            temp[i] = self.data[i]
        self.data = temp

Her bir append işlemi, dizi kapasitesinin dolup dolmadığını kontrol eder. Eğer kapasite dolmuşsa, resize işlemi çağrılır ve dizi boyutu iki katına çıkarılır. Bu, "geometric increase in capacity"nin bir örneğidir.

"Aritmetik ilerleme konusunda dikkatli olun" ifadesi, bir dizi veya listenin boyutunun aritmetik bir ilerleme ile (örneğin, her adımda sabit bir miktarla) artırılması durumunda potansiyel bir verimsizlik durumuna işaret eder.

Aritmetik ilerleme stratejisi, bir dizi veya listenin kapasitesi aşıldığında boyutunu sabit bir miktarda artırır. Örneğin, her seferinde boyutunu 10 birim artırabiliriz. Bu strateji, başlangıçta basit ve cazip görünebilir, ancak büyük veri setleri ile çalışırken zaman ve alan açısından verimsiz olabilir.

Problem, aritmetik ilerlemenin, dizi boyutunu artırmak için gereken yeniden boyutlandırma işlemlerinin sayısını artırmasıdır. Her yeniden boyutlandırma işlemi, tüm öğelerin yeni bir alana kopyalanmasını gerektirir, bu da zaman alır. Bu yüzden, boyutunu sabit bir miktarla artırmak yerine, genellikle boyutunu bir katsayı (genellikle iki) ile artırmak daha verimli olur. Bu, "geometrik ilerleme" stratejisi olarak adlandırılır ve daha önce bahsettiğimiz gibi, dizinin boyutunu artırmak için gereken yeniden boyutlandırma işlemlerinin sayısını azaltır.

Bu nedenle, büyük veri setleriyle çalışırken, genellikle dinamik dizilerin boyutunu artırmak için geometrik bir strateji kullanılır.

Bir dizi veya liste, genellikle gerektiğinden daha fazla hafıza kapasitesine sahip olacak şekilde boyutlandırılır. Bu ekstra kapasite, diziye yeni öğeler eklediğimizde, her ekleme için yeni bir hafıza tahsisine gerek kalmamasını sağlar. Ancak, bir dizi ya da listenin boyutunu artırmak için kullanılan stratejiye bağlı olarak, bazen gereksiz yere büyük miktarda hafıza tahsis edilebilir.

Bir dizi küçüldüğünde, yani içindeki öğeler çıkarıldığında, genellikle ekstra kapasitesi korunur. Bu, diziyi gerektiğinde hızlı bir şekilde genişletebilmek için yapılır. Ancak, bu ekstra kapasite zamanla çok büyük bir hafıza israfı olabilir, özellikle de dizi büyük ölçüde küçültüldüyse.

Bu nedenle, bazı durumlarda, bir dizi küçültüldüğünde hafızayı geri almak için bir mekanizma olabilir. Örneğin, Python'un `list` sınıfı, bir listenin boyutu belirli bir eşiği aştıktan sonra, listenin boyutunu otomatik olarak küçültür. Bu, hafıza kullanımını daha verimli hale getirir, ancak bu özellik her dil veya her dizi/liste uygulamasında mevcut olmayabilir.

Bu tür otomatik hafıza yönetimi genellikle bir dizi veya listenin uygulamasına dahil edilmiş bir özelliktir ve genellikle kullanıcının kontrolü dışındadır. Ancak, bazı durumlarda, bir dizi veya listenin boyutunu manuel olarak küçültmek için bir yol olabilir. Bu genellikle, bir dizi veya listenin kapasitesini belirli bir değere ayarlamak için bir metod çağırarak yapılır. Bu tür bir metod genellikle "shrink", "trim", "compact" veya benzeri bir isme sahiptir.

Öte yandan, hafıza kullanımını optimize etmek için bazen diziye veya listeye eklenen veya çıkarılan öğelerin sayısını kontrol etmek daha etkilidir. Bir diziye çok fazla öğe eklemek ve sonra bunları çıkarmak yerine, gerekli olan minimum sayıda öğeyi eklemek ve çıkarmak genellikle daha verimlidir.