Amortize Analiz
Amortize analiz, en kötü durumdaki bir işlem dizisi boyunca işlem başına ortalama maliyeti sınırlar ve ara sıra pahalı olan işlemlerin maliyetleri birçok ucuz işleme yayıldığında ucuz olabileceğini göstermektedir.
Tanım
Amortize analiz, bir veri yapısı üzerindeki bir işlem dizisinin toplam maliyetini sınırlamak ve işlem sayısına bölerek, bireysel işlemlerin maliyetleri büyük ölçüde farklılık gösterse bile tüm dizi boyunca en kötü durumda geçerli olan işlem başına amortize maliyeti elde etmek için kullanılan bir yöntemdir.
Kapsam
Bu kapsam, amortize analizin üç standart tekniğini — toplama yöntemi, muhasebe (bankacı) yöntemi ve potansiyel yöntemi — ve bunların maliyetleri değişen bireysel işlemlere sahip veri yapılarına (dinamik diziler, ikili sayıcılar, splay ağaçları ve ayrık küme (union-find) yapısı gibi) uygulamalarını ele almaktadır. Amortize maliyeti, ortalama durum maliyetinden ve işlem başına en kötü durum maliyetinden ayırmaktadır.
Temel sorular
- Amortize maliyet, işlem başına en kötü durum maliyetinden ve ortalama durum maliyetinden nasıl farklılık göstermektedir?
- Toplama yöntemi, bir işlem dizisinin toplam maliyetini nasıl sınırlandırmaktadır?
- Muhasebe yöntemi, daha sonraki pahalı işlemlerin ödenmesi için kredileri nasıl atamaktadır?
- Potansiyel yöntemi, maliyetleri dengelemek için bir potansiyel fonksiyonunu nasıl kullanmaktadır?
- Hangi veri yapıları, işlem başına sınırlamalardan ziyade amortize garantilere dayanmaktadır?
Anahtar kavramlar
- amortize maliyet
- toplama yöntemi
- muhasebe (bankacı) yöntemi
- potansiyel yöntemi
- potansiyel fonksiyonu
- dinamik dizi ikiye katlama
- ikili sayıcı artırımı
- yol sıkıştırmalı union-find
Temel kuramlar
- Potansiyel yöntemi
- Potansiyel yöntemi, veri yapısının durumuna negatif olmayan bir potansiyel atamaktadır; bir işlemin amortize maliyeti, gerçek maliyeti artı potansiyeldeki değişimdir, böylece ucuz işlemler, daha sonraki pahalı işlemleri karşılayacak potansiyeli oluşturmaktadır.
- Muhasebe (bankacı) yöntemi
- Muhasebe yöntemi, bazı işlemleri gerçek maliyetlerinden daha fazla ücretlendirmekte, fazlalığı veri yapısı elemanları üzerinde kredi olarak depolayarak gelecekteki pahalı işlemleri karşılamakta ve kredinin asla negatife düşmemesini sağlamaktadır.
Klinik önem
Amortize analiz, ara sıra maliyetli işlemlere rağmen birçok yaygın olarak kullanılan yapının pratikte neden verimli olduğunu açıklamaktadır: dinamik diziler (yeniden boyutlandırılabilir listeler), yeniden karma yapan hash tabloları, bağlantı ve minimum kapsayan ağaç algoritmalarında kullanılan union-find ve splay ağaçları gibi kendi kendini ayarlayan yapılar, işlem başına garantilerden ziyade amortize garantilere dayanmaktadır.
Tarihçe
Amortize analiz terimi ve sistematik çerçevesi, daha önceki ad hoc argümanlardan yararlanılarak Robert Tarjan tarafından 1985 yılında tanıtılmıştır. Bu teknik, 1980'lerde Tarjan ve Sleator tarafından geliştirilen kendi kendini ayarlayan veri yapılarının (splay ağaçları, Fibonacci yığınları) analizinde merkezi bir rol oynamıştır.
Öne çıkan isimler
- Robert Tarjan
- Daniel Sleator
İlgili konular
Temel eserler
- tarjan1985amortized
- cormen2009
Sıkça sorulan sorular
- Amortize maliyet, ortalama durum maliyeti ile aynı mıdır?
- Hayır. Ortalama durum maliyeti, girdilerin bir olasılık dağılımı üzerindeki bir beklentidir ve şanssız bir girdi tarafından ihlal edilebilmektedir. Amortize maliyet ise, rastgelelik varsayılmayan bir işlem dizisi üzerinde en kötü durum garantisidir: böyle herhangi bir dizinin toplam maliyeti sınırlıdır, bu nedenle işlem başına ortalama her zaman geçerlidir.
- Dinamik bir diziye ekleme işlemi, yeniden boyutlandırma O(n) iken neden amortize O(1) olmaktadır?
- Çünkü dizi genellikle kapasitesini ikiye katlamaktadır, yeniden boyutlandırmalar eklemelere göre nadirdir ve n adet ekleme dizisi boyunca toplam kopyalama işi n ile orantılıdır. Tüm eklemelere yayıldığında, tek bir yeniden boyutlandırma doğrusal olsa bile sabit bir amortize maliyet sağlamaktadır.