Amortized Algorithm Analysis (İtfa Tahlili, amotize algoritma analizi)

Yazan : Şadi Evren ŞEKER

Bilgisayar bilimlerinde algoritma performansının değerlendirilmesinde kullanılan yöntemlerden birisidir. Kısaca, bir algoritmanın en kötü durumunu araştırırken (worst case analysis) en kötü durumun olma ihtimallerinin de beraberinde incelendiği tahlil yöntemidir.

Klasik bir en kötü durum analizi (worst case analysis) yöntemi algoritmanın çalışacağı en kötü durumu ortaya atar ve buradaki performansı ölçer. Örneğin kabarcık sıralaması (bubble sort) ele alalım. Bu algoritma için en kötü durum sıralanacak olan grubun tersten sıralı olarak verilmesidir (küçükten büyüğe doğru sıralamak istediğimiz bir örneğin, tam ters sıralı olarak büyükten küçüğe sıralı olması durumudur).

Ancak itfa tahlil (amortized analysis) yöntemi ile bu en kötü durumun olma ihtimali de göz önünde bulundurulur. Bu durumu daha basit bir örnek üzerinden anlatmaya çalışalım.

Örnek Değişken boyutlu dizi (Dynamic Array)

Bir değişken dizi uygulaması sırasında (dynamic array) hafızada dizinin ne kadar yer kaplayacağı önceden bilinemez. Amacımız hafızada eklenen eleman sayısı arttıkça kapladığı yeri artan bir dizi kodlamaktır. Örneğin tek eleman eklenmesi halinde hafızada tek eleman, beş eleman eklenmesi halinde ise hafızada beş elemanlık yer kaplayan bir dizi kodlamak istiyoruz.

Bu dizi kodlamasının en klasik uygulaması, dizi için hafızada ayrılan yerin dolması halinde, hafızadaki kaplanan yerin iki misline çıkarılmasıdır. Ayrıca iki misline çıkınca önceki dizide bulunan verilerin, yeni diziye kopyalanması da gerekmektedir. Örneğin hafızada iki elemanlı yer ayırarak başladık, 2 eleman dolduğunda hafızadaki yeri 4 elemana çıkarıyoruz, ve eski dizideki iki elemanı, yeni diziye kopyalıyoruz, 4 eleman dolduğunda 8 elemana çıkarıyoruz ve eski dizideki 4 elemanı yeni diziye kopyalıyoruz v.b.

Şimdi eleman ekleme işleminin hafızadaki karmaşıklığına bakalım. En kötü durum analizi bize, analiz sırasında karşılaşılabilecek en kötü durumu hesaplamamız gerektiğini söyler. Buna göre en kötü durum hafızanın dolması ve yeni yer açılmasıdır. Dizimizde n eleman olduğunu kabul edersek dizi dolduğu anda n elemanlık bir yer daha açılacaktır. Bu durumda algoritma karmaşıklığımızın O(n) olduğunu söyleyebiliriz. En kötü durum analizine göre doğru olan bu yaklaşım, itfa tahlilinde (amortize algoritma analizi) geçerli değildir.

Algoritmamızın çalışması sırasında n. elemanın eklenmesi için yeni açılan diziye n eleman kopyalanacaktır. Bu kopyalama işleminden sonra dizimize n adet eleman daha alabileceğiz. Dolayısıyla 2n elemanı eklemek için n adet kopyalama işlemine ihtiyaç duyuyoruz. O halde basit bir hesaplama ile 2n elemanın eklenmesi için 2n işlem + n adet kopyalama = 3n işlem yapmaktadır. Karmaşıklık ise basitçe O(3n/2n) = O(3/2) = O(1) olarak bulunur (sabit değerlerin big-oh değerinin 1 olduğunu hatırlayınız örneğin O(20) = O(1) )

Yukarıdaki işlem sırasında akla gelebilecek bir soru, n adet elemanın eklenmesi işleminin altında da kopyalama işlemleri yapıldığıdır. Örneğin 16 eleman eklenmesi için kaç adım gerektiğini hesaplayalım:

2 eleman eklenir

2 eleman daha eklemek için 2 kopyalanır 2 eklenir: toplam 4 eklenmiş 2 kopyalanmıştır

4 eleman daha eklemek için 4 kopyalanır 4 eklenir: toplam 8 eklenmiş 6 kopyalanmıştır

8 eleman daha eklemek için 8 kopyalanır 8 eklenir: toplam 16 eklenmiş 14 kopyalanmıştır

Yukarıdaki gidişten anlaşılacağı üzere n ekleme için yaklaşık olarak n kopyalama yapılmaktadır. Yani limit alındığında ve eklenen elemanların sayısı sonsuza götürüldüğünde kopyalanan elemanların sayısı neredeyse eklenen elemanların sayısına eşit çıkacaktır. O halde her yeni eleman eklenmesinin maliyeti 1’e daha da yaklaşacaktır (n / n = 1 olduğu için)

Örnek : Binom Sırası (Binomial Queue)

Farklı bir örnek olarak Binom Sırasına bakalım (binomial queue).

Öncelikle sıranın nasıl ilerlediğini hatırlayalım :

B0:

B1:

B2:

B3:

B4:

Yukarıda görüldüğü üzere, her binom sırasında, o ana kadar olan sıraların tamamı içerilmektedir. Örneğin B4’ün kolları, sırasıyla B0, B1, B2, B3 ağaçlarını barındırmaktadır.

Bu durumda i. Terim için aşağıdakine benzer bir hesaplama sayısı gerekmektedir:

T(i) = T(i-1) + 2 – C

ve T(0) = 0

Yukarıdaki özyineli formülde (recursive function) i. adım için T(i) adet ağaç gerekmektedir. Elbette bu sayı da T(i-1) ile gösterilen ve i. adım öncesinde bulunan ağaç sayısına 2-C eleman eklenerek bulunmaktadır. Bu denklemdeki C ile gösterilen değer, i. adımın maliyetini (bilgisayardaki hesaplama işlem maliyeti, hafıza maliyeti vs. ) göstermektedir.

Yukarıdaki işlemi biraz daha ilerletirsek :

C + T(i) – T(i-1) = 2

sonucunu bulur ve buradan bütün denklemleri yazıp toplarsak, n adet eleman için işlem maliyetini aşağıdaki şekilde bulabiliriz:

C ₁ + T(1) – T(0) = 2

C ₂ + T(2) – T(1) = 2

C ₃+ T(3) – T(2) = 2

…

C _n-1+ T(n-1) – T(n-2) = 2

C _n + T(n) – T(n-1) = 2

Yukarıdaki denklemlerin toplamı olarak:

Ayrıca ilk denklem olarak T0 = 0 olduğunu biliyoruz çünkü binom ağacının ilk elemanı 0 çocuk sahibidir.

Dolayısıyla yukarıda bulduğumuz n eleman için 2n maliyeti bize yine itfa tahlili ile O(2n /n) = O(2) = O(1) sonucunu gösterir. Klasik bir en kötü durum analizi ile, bu hesaplamada, O(n) maliyet çıkaracaktık ancak amortize analiz bize burada bir adım ilerisini göstererek en kötü durumun tahlil edilmesinin aslında tek elemana bakılarak yapılamayacağını ve bütün elemanlar incelendiğinde aslında en kötü durumun o kadar da kötü olmadığını göstermektedir 🙂

Ortalama durum ile Amortize algoritma analizinin farkı.

Bu anlamda ortalama durum analizinden (average case analysis) ayrılmaktadır. Yani ortalama durum analizinde bütün ihtimallerden ortalama maliyette bir ihtimal üzerinden analiz yapılır. Bütün ihtimaller hesaplanarak ortalamaları bulunur. Amortisman analiz yönteminde ise hala en kötü durumu analiz etmekteyiz ancak analizi bir adım daha genişleterek en kötü durumun beklenenden daha iyi olduğunu ispatlıyoruz. Yukarıdaki iki örnek için de , yani binom yığıtı (binomial heap) veya değişken boyutlu dizi (dynamic array) için de tek elemanın eklenmesi halinde yapılan en kötü durum analizinden daha iyi sonuçlar bulduk ancak bu sonuçlar hala en kötü durumda bulunacak sonuçlardır. Tek farkı en kötü durum analizinde tek bir elemana bakılmaktayken amortize algoritma analizinde olayın geneline baktık.

İtfa Tahlili Yöntemleri:

İtfa tahlilinde kullanılan 3 klasik yöntem bulunmaktadır.

Münasebet tahlili (aggregate analysis). Bu tahlil yönteminde, n terim için olan maliyet, özyineli bir fonksiyon olarak yazılır, örneğin T(n) olarak isimlendirelim ve bu değer n terime bölünür, örneğin T(n) / n değeri olarak hesaplanır. Yukarıdaki örneklerden binom ağacı (binomial tree) bu yöntemle tahlil edilmiştir.

Muhasebe tahlili (accounting analysis). Bu yöntemde, her ilave işlemin sisteme getirdiği yük anlık olarak hesaplanır. Örneğin n terimden sonra n+1 terim olduğunda ne kadar yükte değişiklik olacağı anlaşılmaya çalışılır. Sabit uzunlukta çalışma örnekleri alınarak sisteme getirdiği maliyete her elemanın etkisi ölçülür ve buradan n elemanlı bir çalışmaya maliyet genellemesi yapılır. Yukarıdaki örneklerden değişken boyutlu dizi (dynamic array) bu tahlile bir örnektir ve örnekte görüldüğü üzere 2,4,8,16 gibi çalışma uzunlukları alınarak bir genelleme yapılmıştır.

Kapasite tahlili (potential analysis). Bu yöntem, muhasebe tahlili ile tamamen aynıdır. Bu tahlil yönteminde de elemanlara bakılmak suretiyle genelleme yapılmaya çalışılır. Muhasebe tahlilinden tek farkı her elemanın sisteme yaptığı etkinin bir ödeme değil bir kapasite azalması olarak görülmesidir. Bu noktayı biraz açmak gerekirse:

Muhasebe tahlili ile kapasite tahlili aslında algoritma analizine muhasebe dünyasından girmiş yöntemlerdir. Muhasebede kullanılan ve bir birikim fonksiyonunu tahlil etmek için (debit function) kullanılan iki yaklaşımdan birisi, birikimi bir ödeme olarak görmek ve her adımda ödeme yapılmak suretiyle birikimi arttırmak iken ikincisi birikimi bir kapasite olarak görmek ve her adımda bu kapasiteyi azaltmak olarak görmektir.

Aslında ikisi de aynı değeri hesaplamaktadır ancak birincisi her adımda değerleri biriktirmekte, ikincisi ise başta birikimi hesaplayıp her adımda bu birikimi eksiltmektedir.

Yukarıdaki örneklerden değişken boyutlu diziyi (dynamic array) hatırlayacak olursak, bu dizideki maliyeti hesaplarken her elemanın sisteme etkisini bulmuştuk. Bazı elemanlar sisteme 1 etkisi yaparken bazı elemanlar n etkisi yapmıştı. Yani 2,4,8 gibi elemanlarda o ana kadar olan eleman kadar etki yapılmıştı. Ancak örneğin 1,3,5,6,7 gibi sayıların sisteme maliyeti 1 idi. Bu yaklaşım, muhasebe yaklaşımı olup, her elemanın sisteme artan miktardaki etkisi biriktirilmektedir.

Bu yaklaşımın tersi bir yorumla, ilk başta 2n maliyet getireceğini kabul edip (2n değerinde borç kredi aldığımızı kabul edin) her adımda bu değeri düşürmek (her adımın maliyetini kredimize geri ödeme olarak düşünüyor ve kredi borcumuzu kapatıyoruz) ise kapasite yaklaşımıdır (potential analysis).