Teorema master tidak berlaku?

Diberikan persamaan rekursif berikut

kita ingin menerapkan teorema Master dan perhatikan itu

T (n) = 2 T (\frac{n}{2}) + n \log n

$T(n) = 2T\left(\frac{n}{2}\right)+n\log n$

n^{\log_{2} (2)} = n .

$n^{\log_2(2)} = n.$

Sekarang kita periksa dua case pertama untuk , yaitu apakah $\varepsilon > 0$

atau $n\log n \in O(n^{1-\varepsilon})$
. $n\log n \in \Theta(n)$

Kedua kasus tidak puas. Jadi kita harus memeriksa kasus ketiga, yaitu apakah

. $n\log n \in \Omega(n^{1+\varepsilon})$

Saya pikir kondisi ketiga juga tidak terpenuhi. Tapi kenapa? Dan apa penjelasan yang bagus mengapa teorema Tuan tidak bisa diterapkan dalam kasus ini?

proof-techniques asymptotics recurrence-relation master-theorem Joachim
sumber

Lihat kasus 2 bentuk umum di wiki .

Kasus tiga tidak puas karena

tidak

untuk

. Gunakan aturan l'Hôpital pada

batas

\log n

$\log n$

Ω (n^{ϵ})

$\Omega(n^\epsilon)$

ϵ > 0

$\epsilon > 0$

\frac{\log n}{n^{ϵ}}

$\frac{\log n}{n^{\epsilon}}$

sdcvvc

Setelah Anda menunjukkan bahwa tidak ada kasus yang berlaku, itu adalah bukti bahwa Anda tidak dapat menerapkan teorema master seperti yang dinyatakan.

Raphael

Siapa yang butuh Teorema Master? Gunakan pohon rekursi.

JeffE

Pertanyaan serupa pada math.SE .

Raphael

Jawaban:

Tiga kasus Teorema Master yang Anda rujuk dibuktikan dalam Pengantar Algoritma oleh Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest dan Clifford Stein (Edisi ke-2, 2001).

Telah diamati dengan benar bahwa perulangan yang dimaksud jatuh antara Kasus 2 dan Kasus 3. Yaitu tumbuh lebih cepat dari tetapi lebih lambat dari untuk setiap . $f(n) = n \log n$ $n$ $n^{1+\varepsilon}$ $\varepsilon > 0$

Namun teorema dapat digeneralisasi untuk menutupi pengulangan ini. Mempertimbangkan

$f(n) = \Theta (n^{\log_b a }\log_b^k n)$ $k\geq 0$

$k = 0$ $f(x)$ $\Theta (\log_b n)$

T (n) = Θ (n^{\log_{b} a} \log_{b}^{k + 1} n)

$T(n) = \Theta (n^{\log_b a }\log_b^{k+1} n)$

Dalam Pengantar algoritma pernyataan ini dibiarkan sebagai latihan.

T (n) = Θ (n \cdot \log^{2} n) .

$T(n) = \Theta(n \cdot \log^2 n).$

Rincian lebih lanjut tentang Teorema Master dapat ditemukan di halaman Wikipedia yang luar biasa .

lim_{x \to c} \frac{f (x)}{g (x)} = lim_{x \to c} \frac{f^{'} (x)}{g^{'} (x)}

$\lim_{x\to c} \frac{f(x)}{g(x)} = \lim_{x\to c} \frac{f^\prime(x)}{g^\prime(x)}$

f (x)

$f(x)$

g (x)

$g(x)$

c

$c$

f (n) = n \log n

$f(n) = n \log n$

g (n) = n^{1 + ε}

$g(n) = n^{1+\varepsilon}$

\log n \notin Θ (n^{1 + ε}) .

$\log n \not\in \Theta (n^{1+\varepsilon}).$

Sketsa Bukti Teorema Master untuk Kasus 2A.

Ini adalah reproduksi bagian dari bukti dari Pengantar ke Algoritma dengan modifikasi yang diperlukan .

Pertama kita buktikan Lemma berikut.

Lemma A:

g (n) = \sum_{j = 0}^{\log_{b} n - 1} a^{j} h (n / b^{j})

$g(n) = \displaystyle \sum_{j=0}^{\log_b {n-1}} a^j h(n/b^j)$

h (n) = n^{\log_{b} a} \log_{b}^{k} n .

$h(n) = n^{\log_b a} \log_b^k n.$

g (n) = n^{\log_{b} a} \log_{b}^{k + 1} n .

$g(n) = n^{\log_b a} \log_b^{k +1} n.$

$h(n)$ $g(n)$

g (n) = n^{\log_{b} a} \log_{b}^{k} n \sum_{j = 0}^{\log_{b} n - 1} {(\frac{a}{b^{\log_{b} a}})}^{j} = n^{\log_{b} a} \log_{b}^{k + 1} n .

$g(n) = \displaystyle n^{\log_b a} \log_b^k n \; \sum_{j=0}^{\log_b{n-1}} \left(\frac{a}{b^{\log_b a}}\right)^j = n^{\log_b a} \log_b^{k +1} n.$

QED

$n$ $b$

T (n) = a T (n / b) + f (n), T (1) = Θ (1)

$T(n) = a T(n/b) + f(n),\quad T(1) = \Theta(1)$

T (n) = Θ (n^{\log_{b} a}) + \sum_{j = 0}^{\log_{b} n - 1} a^{j} T (n / b^{j}) .

$T(n) = \Theta(n^{\log_b a}) + \displaystyle \sum_{j=0}^{\log_b n - 1} a^j T(n/b^j).$

f (n)

$f(n)$

Θ (n^{\log_{b} a} \log_{b}^{k} n)

$\Theta(n^{\log_b a} \log_b^k n)$

Θ

$\Theta$

T (n) = Θ (n^{\log_{b} a} \log_{b}^{k + 1} n) .

$T(n) = \Theta (n^{\log_b a }\log_b^{k+1} n).$

$n$ $b$

Dmitri Chubarov
sumber

Teorema Akra-Bazzi adalah generalisasi ketat dari teorema master. Sebagai bonus, buktinya adalah badai integral yang akan membuat kepala Anda berputar ;-)

$T(n) \sim g(n)$

vonbrand
sumber