sönümlü analiz

Bu makale bilgisayarlar hakkında bir taslaktır .

İlgili projelerin tavsiyelerine göre bilginizi geliştirerek ( nasıl ? ) paylaşabilirsiniz .

Olarak bilgisayar biliminin , itfa edilmiş analizi bir üzerindeki işlemlerin geçici karmaşıklığı değerlendirilmesi için bir yöntemdir veri yapısı . Bu analiz, algoritmaların sınıflandırılmasıyla sonuçlanır ve sönümlü karmaşıklık adı verilen algoritmaların karmaşıklığına ilişkin belirli bir teoriye yol açar .

İtfa edilmiş analiz pahalı ve kılıflar nadiren gizli ve ucuz davaları telafi dikkate alarak bu artışın her ortalama işlem atamak için işlemler dizisiyle kümülatif maliyetini artırmak için aslında. Kullanılabilir olması için bu analiz, en pahalı durumların sıklığını sınırlayabileceğimizi varsayar. İtfa edilmiş analiz, en kötü duruma yerleştirilir ve bu durumda her işlemin ortalama performansını garanti eder . Amorti edilmiş analizden verimli veri yapıları tasarlanabilir.

Tanım

Sönümlü analiz, aynı veri yapısı üzerinde gerçekleştirilen bir dizi işlemin (zamansal) karmaşıklığını inceler. Çoğu işlemin ekonomik olduğu gerçeğini göz önünde bulundurarak, belirli pahalı işlemlerin ek maliyetini tüm işlemlere dağıtır. Bir dizideki her işleme, tüm bu işlemler üzerinden toplam maliyetin aritmetik ortalaması olan itfa edilmiş bir maliyet atar . İşlemler arasındaki denkleştirmeler (zaman içindeki ucuz işlemler, maliyetli işlemleri denkleştiren) dikkate alındığında, bu süre genel olarak, en kötü durum analizinin vereceği süreden önemli ölçüde daha iyidir.

By yayılan tüm işlemleri üzerinde belli operasyonların yüksek maliyet, bu makul bir ortalama maliyet her operasyon ile ilişkili olacağını bekliyor. Dağıtım operasyon dizisinin maliyetinin benziyor damperi muhasebe alanında. Bu analizin sonucu, her işlemin ortalama performansında bir artıştır.

Bu analiz, dahili durumundaki yeniden dengelemeler veya iyileştirmeler gibi sık olmayan işlemler sırasında önemli maliyetler içeren bir veri yapısını incelerken faydalı bir şekilde kullanılır. İtfa edilmiş analiz, daha sonra, bu işlem bir yürütme dizisinde pahalı olsa bile, bir işlemin ortalama maliyetinin düşük olduğunu göstermek için kullanılabilir. Dolayısıyla bu yaklaşımın amacı, bir dizi operasyondan en pahalı operasyonlara kendilerine ait olan (yani diğerleriyle karşılaştırılabilir) ağırlığı verirken karmaşıklıkta bir artış sağlamaktır. Temel olarak, pahalı işlemler pahalıdır çünkü veri yapısını arada bir yeniden düzenlerler, bu da diğer tüm işlemlere fayda sağlar ve analiz onları "cezalandırmaz".

uygulama

En belirgin yöntem, bir dizi işlemi gerçekleştirmek için gereken toplam süre için bir üst sınır hesaplamak için doğrudan bir argüman kullanmaktır. Bir algoritmanın sönümlü karmaşıklığını belirlemek için üç yöntem kullanılabilir:

Agregasyon yöntemi , en kötü durum işlemler aritmetik bir ortalama olarak her bir işlemin itfa edilmiş maliyetini hesaplar. İtfa edilmiş maliyet, bu nedenle, ortalama maliyetin bir artışıdır. Bu yöntem, her işleme aynı itfa edilmiş maliyeti atar.

Muhasebe yöntemi karmaşık işlemlerin maliyeti onlar neden olacaktır basit işlemlere “ödeme yapar”. Bir süitteki belirli yardımcı işlemlerin ek maliyeti, bu nedenle, bunların kaynağı olanlarla tamamen dengelenir.

Potansiyel yöntem “ücretleri” muhasebe yönteminde olduğu gibi veri yapısına maliyetleri ve artık her operasyon için. Kavramsal olarak, gelecekteki belirli operasyonların ek maliyetini tahmin etmek için zamanla serbest bırakılan bir potansiyele (“sermaye”) dayanır.

Ortalama vaka analizinden farklılıklar

İtfa edilmiş analiz , aşağıdaki nedenlerle ortalama vaka analizinden farklıdır :

Örnek: dinamik tablolar

Sönümlü analiz, dinamik bir diziye eklemek için bir algoritmanın zaman karmaşıklığını hesaplayarak gösterilebilir. Basitleştirmek için, veri yapısının, üzerinde mevcut tek işlemin yerleştirme olduğu birkaç on hücreden oluşan bitişik bir bellek bölgesi (bir dizi) olduğunu kabul edeceğiz. Gerekirse bu dizinin boyutu artabilir. Bir eleman eklerken, dizi hala en az bir boş hücre kabul ediyor veya tamamen dolu. İlk durumda, yeni elemanın eklenmesi basit bir kopyalama işleminde yapılır. İkinci durumda, önce boyutu önceki diziden daha büyük olan yeni bir dizi oluşturmanız, ardından eski dizinin öğelerini kopyalamanız ve ardından eklenecek öğeyi eklemeniz gerekir.

Dizi dolu olmadığı sürece, en yaygın durum, toplama işlemi iki işlem sayesinde sabit zamanda yapılır: yeni elemanın ilk boş hücreye yazılması ve diziyi doldurmak için sayacın artırılması.

Öte yandan, dizi dolduğunda, nadir bir durum, yeni bir dizi tahsis etmek ve tüm öğeleri kopyalamak gerekir; Bu işlemin "klasik" karmaşıklığı O (n) 'dedir, burada n , geçerli dizinin boyutudur.

Sönümlü analiz, dizinin boyutundaki artışın neden olduğu ek maliyet nadiren meydana geldiğinden, doğal olarak bu tür algoritma için geçerlidir. Eğer n, dizinin ilk boyutu, itfa yeniden tahsisini eşit üzerinde boyutu artış maliyetini dağıtma oluşur , n ilk eklemeler.

Tablonun n artış katsayısını uygun bir şekilde seçerek, tam bir tabloya ekleme maliyetinin global olarak marjinal kalması garanti edilebilir, bu da amortismana tabi ortalama için bir maliyet O(1)'e yol açar . Her kusur için dizinin boyutunu iki katına çıkarmak iyi bir taktiktir.

Algoritma tasarım tekniği

Tarihi

Sönümlü analizin ilk kullanımlarından biri , ikili ağaç aramasının bir varyasyonu için Robert Tarjan tarafından yapılmıştır . Union-Find veri yapısı başarılı bir şekilde analiz edilerek popüler hale getirildi .

Notlar ve referanslar

  1. (içinde) Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest ve Clifford Stein , Algoritmalara Giriş , MIT Press ,2009, 3 e  ed. [ basımın detayı ]. Bölüm 17, s. 472.
  2. en kötü durumda karmaşıklık, belirli bir yürütme sırasında algoritmayı aşırı bir şekilde davranmaya zorlayan pahalı işlemleri vurgulayan kötümser bir sınırdır.
  3. İngilizce Dinamik dizideki makalenin geometrik genişlemesi ve itfa edilmiş maliyeti paragrafına bakın .
  4. Algoritmaların tasarımına ve analizine giriş, Pearson, 2011, Anany Levitin, 3. baskı, s. 49
  5. Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest ve Clifford Stein , Algoritmiklere Giriş , Dunod ,2002[ basımın detayı ]Bölüm 17. Notlar. P. 419.

Şuna da bakın:

bibliyografya