Tekrarlama Bağıntıları
Tekrarlama bağıntıları, özyinelemeli bir algoritmanın çalışma süresini, daha küçük girdilerdeki çalışma süresi cinsinden ifade etmektedir; bunların çözülmesi, böl ve yönet (divide-and-conquer) ve diğer özyinelemeli algoritmaları analiz etmek için kullanılan kapalı formdaki asimptotik sınırları sağlamaktadır.
Tanım
Tekrarlama bağıntısı, bir fonksiyonun bir girdideki değerini, daha küçük girdilerdeki değerleri cinsinden tanımlayan bir denklemdir; algoritma analizinde ise, bir algoritmanın n boyutundaki bir girdideki maliyetini, daha küçük alt problemler üzerindeki maliyeti cinsinden ifade etmektedir.
Kapsam
Bu konu, algoritma analizinde ortaya çıkan tekrarlama bağıntılarının formülasyonunu ve çözümünü kapsamaktadır: yerine koyma yöntemi (substitution method), özyineleme ağacı yöntemi (recursion-tree method) ve T(n) = aT(n/b) + f(n) formundaki böl ve yönet tekrarlama bağıntıları için ana teorem (master theorem). Her özyinelemeli algoritmanın nasıl bir tekrarlama bağıntısı oluşturduğunu ve bu bağıntının nasıl bir büyük-Theta (big-Theta) sınırına dönüştürüldüğünü açıklamaktadır. Asimptotik gösterimin kendisi ayrı olarak ele alındığından bu kapsamın dışındadır; ayrıca ayrık matematikteki kombinatoryal üreteç fonksiyonu yöntemleri de bu kapsamda değildir.
Temel sorular
- Özyinelemeli bir algoritma, çalışma süresi için nasıl bir tekrarlama bağıntısı oluşturmaktadır?
- Yerine koyma yöntemi, tahmin edilen bir çözümü kanıtlamak ve doğrulamak için nasıl kullanılmaktadır?
- Özyineleme ağacı yöntemi, özyineleme seviyelerindeki toplam işi nasıl ortaya koymaktadır?
- Ana teorem ne zaman uygulanır ve üç durumu ne anlama gelmektedir?
- Ana teoremin formunun dışında kalan tekrarlama bağıntıları nasıl ele alınmaktadır?
Anahtar kavramlar
- tekrarlama bağıntısı
- yerine koyma yöntemi
- özyineleme ağacı yöntemi
- ana teorem
- böl ve yönet tekrarlama bağıntısı
- temel durum ve özyinelemeli durum
- kapalı form çözüm
- Akra-Bazzi yöntemi
Temel kuramlar
- Ana teorem
- Böl ve yönet tekrarlama bağıntıları T(n) = aT(n/b) + f(n) için ana teorem, f(n)'yi n'nin log taban b'de a üssü ile karşılaştırarak asimptotik çözümü vermektedir; bu, yaprakların, kökün veya dengeli seviyelerin baskın olduğu üç durumu kapsamaktadır.
- Özyineleme ağacı ve yerine koyma yöntemleri
- Özyineleme ağacı yöntemi, her özyineleme seviyesinde yapılan işi toplayarak bir sınır önermektedir; bu sınır, yerine koyma yöntemi tarafından tümevarım yoluyla titizlikle kanıtlanmaktadır; bu iki yöntem birlikte, ana teoremin kapsamı dışındaki tekrarlama bağıntılarını ele almaktadır.
Klinik önem
Tekrarlama bağıntılarının çözümü, birleştirme sıralaması (mergesort) ve hızlı sıralama (quicksort) gibi algoritmalar ile hızlı çarpma ve birçok dinamik programlama algoritması gibi özyinelemeli algoritmaların çalışma süresini belirlemede standart bir yöntemdir. Mühendisler ve araştırmacılar, bu tür algoritmalara ilişkin asimptotik karmaşıklık iddialarını türetmek ve doğrulamak için ana teoremi rutin olarak kullanmaktadır.
Tarihçe
Algoritmaların tekrarlama analizi, Knuth'un The Art of Computer Programming adlı eserinde sistemleştirilmiştir. Ana teorem, CLRS aracılığıyla ders kitaplarının temel bir parçası haline gelmiş ve Akra-Bazzi yöntemi (1998) ise onu, eşit olmayan bölümlere sahip daha geniş bir böl ve yönet tekrarlama bağıntıları sınıfına genelleştirmiştir.
Öne çıkan isimler
- Donald Knuth
- Mohamad Akra
- Louay Bazzi
İlgili konular
Temel eserler
- cormen2009
- knuth1997vol1
Sıkça sorulan sorular
- Ana teoremi ne zaman kullanabilirim?
- Ana teorem, a >= 1 ve b > 1 olmak üzere T(n) = aT(n/b) + f(n) formundaki tekrarlama bağıntılarına uygulanmaktadır; burada her seviye problemi n/b boyutunda a alt probleme bölmektedir. Eşit olmayan bölümlere, değişen alt problem boyutlarına veya polinom olmayan birleştirme maliyetlerine sahip tekrarlama bağıntıları için bunun yerine özyineleme ağacı, yerine koyma veya Akra-Bazzi yöntemleri gerekebilmektedir.
- Birleştirme sıralamasının (mergesort) tekrarlama bağıntısı neden O(n log n) vermektedir?
- Birleştirme sıralaması (mergesort), T(n) = 2T(n/2) + O(n) sonucunu vermektedir: iki yarı boyutlu alt problem artı doğrusal birleştirme. Burada, özyineleme ağacının tüm log n seviyelerinde seviye başına yapılan iş aynıdır, bu nedenle toplam iş n çarpı log n'dir; ana teorem bunu Theta(n log n) olarak doğrulamaktadır.