Teorema master tidak berlaku?

11

Diberikan persamaan rekursif berikut

kita ingin menerapkan teorema Master dan perhatikan itu

T(n)=2T(n2)+nlogn

nlog2(2)=n.

Sekarang kita periksa dua case pertama untuk , yaitu apakahε>0

  • ataunlognO(n1ε)
  • .nlognΘ(n)

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

  • .nlognΩ(n1+ε)

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

Joachim
sumber
4
Kasus tiga tidak puas karena tidak Ω ( n ϵ ) untuk ϵ > 0 . Gunakan aturan l'Hôpital pada log batas nlognΩ(nϵ)ϵ>0lognnϵ
sdcvvc
1
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

Jawaban:

7

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 n tetapi lebih lambat dari n 1 + ε untuk setiap ε > 0 .f(n)=nlognnn1+εε>0

Namun teorema dapat digeneralisasi untuk menutupi pengulangan ini. Mempertimbangkan

f(n)=Θ(nlogbalogbkn)k0

k=0f(x)Θ(logbn)

T(n)=Θ(nlogbalogbk+1n)

Dalam Pengantar algoritma pernyataan ini dibiarkan sebagai latihan.

T(n)=Θ(nlog2n).

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

limxcf(x)g(x)=limxcf(x)g(x)
f(x)g(x)cf(n)=nlogng(n)=n1+εlognΘ(n1+ε).

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)=j=0logbn1ajh(n/bj)
h(n)=nlogbalogbkn.g(n)=nlogbalogbk+1n.

h(n)g(n)

g(n)=nlogbalogbknj=0logbn1(ablogba)j=nlogbalogbk+1n.

QED

nb

T(n)=aT(n/b)+f(n),T(1)=Θ(1)
T(n)=Θ(nlogba)+j=0logbn1ajT(n/bj).
f(n)Θ(nlogbalogbkn)Θ

T(n)=Θ(nlogbalogbk+1n).

nb

Dmitri Chubarov
sumber
1

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

T(n)g(n)

vonbrand
sumber