Home › algorithm › Algoritma Tasarımı ve Analizi II (Algorithm Design and Analysis II)

Algoritma Tasarımı ve Analizi II (Algorithm Design and Analysis II)

Burak Tahtacıoğlu

3/10/2016

Rekürsif Denklem Çözme Yöntemleri

1. Tekrarlama Yöntemi (Iteration Method)

2. Rekürsif Ağaç Yöntemi (Recursive Tree Method)

3. Usta Yöntemi (Master Method)

T(n) = T(n-1) + n Θ(n²)

T(n) = T(n/2) + c Θ(lgn)

T(n) = T(n/2) + n Θ(n)

T(n) = T(n/2) + n Θ(n)

T(n) = 2T(n/2) + 1 Θ(n)

Rekürsif Ağaç Yöntemi (Recursive Tree Method)

Egzersiz

T (n) = 2T(n/ 2) +n²

Bu fonksiyon için özyineleme ağacı:

Bu durumda, belirli bir düzeyde yapılan toplam işi elde etmek için ağacın her satırı boyunca toplama işlemi yapılmalıdır.

$i=n/2^{i}\; \; \; seviye \; boyutu$

$(n/2^{i})^{2} \;\;\; her \; node'un \; maliyeti \;$

$2^{i} \;\;\; i \; seviyedeki \; node \; sayisi \;$

$(n/2^{i})^{2}\cdot 2^{i} =n^{2}/2^{i} \;\;\; toplam \; maliyet$

$n/2^{h}=1 \; \; \; (h)$

$h=lgn$

$T(n)=\sum_{i=0}^{lgn}(\frac{n^{2}}{2^{i}})=n^{2}\sum_{i=0}^{lgn}(\frac{1}{2})^{i}\leq n^{2}\sum_{i=0}^{lgn}(\frac{1}{2})^{i}=n^{2}\frac{1}{1-\frac{1}{2}}=2n^{2}\;\; \;$

$T(n)=O(n^{2})$

Bu toplam geometrik seri toplamıdır O (n² ) . Bu durumda ağacın derinliği gerçekten önemli değil; Her düzeyde iş miktarını çok hızlı bir şekilde Toplam sadece sabit bir faktör daha root daha olduğunu azalmaktadır.

Egzersiz

T (n) = T (n / 3) + T (2n / 3) + n

Birkaç seviyeli rekürsif ağaç:

Usta Yöntemi (Master Method)

1. Usta Yöntemi (Master Method)

2. Usta Yöntemi (Master Method)

3. Usta Yöntemi (Master Method)

Egzersiz

T(n) = 2T(n/2) + n

Egzersiz

T(n) = 2T(n/2) + n²

Egzersiz

Egzersiz

T(n) = 3T(n/4) + nlgn

Egzersiz

T(n) = 2T(n/2) + nlgn

Ek-1

Bir sonraki yazımda görüşmek üzere...

Burak Tahtacıoğlu

Tutup Konverter! Emoticon