Bukti yang kuat untuk validitas asumsi

Teorema Master adalah alat yang indah untuk memecahkan beberapa jenis perulangan . Namun, kami sering mengabaikan bagian integral ketika menerapkannya. Misalnya, selama analisis Mergesort kami dengan senang hati pergi dari

$\qquad T(n) = T\left(\left\lfloor \frac{n}{2} \right\rfloor\right) + T\left(\left\lceil \frac{n}{2} \right\rceil\right) + f(n)$

untuk

$\qquad T'(n) = 2 T'\left(\frac{n}{2}\right) + f(n)$

hanya mempertimbangkan . Kami meyakinkan kami sendiri bahwa langkah ini valid - yaitu, - karena berperilaku "baik". Secara umum, kita mengasumsikan untuk penyebut yang sama. $n=2^k$ $T \in \Theta(T')$ $T$ $n=b^k$ $b$

Mudah untuk membuat rekurensi yang tidak memungkinkan penyederhanaan ini dengan menggunakan setan . Misalnya, pengulangan di atas untuk / dengan $f$ $T\,$ $\,T'$

$\qquad f(n) = \begin{cases} 1 &, n=2^k \\ n &, \text{else} \end{cases}$

akan menghasilkan dengan menggunakan teorema Master dengan cara biasa, tetapi jelas ada urutan yang tumbuh seperti . Lihat di sini untuk contoh lain yang lebih rumit. $\Theta(n)$ $\Theta(n \log n)$

Bagaimana kita bisa membuat ini "dengan baik" ketat? Saya cukup yakin monotonisitas sudah mencukupi, tetapi perulangan Mergesort yang sederhana pun tidak monoton; ada komponen periodik (yang didominasi tanpa gejala). Apakah cukup untuk menyelidiki , dan kondisi apa yang diperlukan dan memadai pada yang memastikan teorema Master bekerja? $f$ $f$

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

Lain mengambil hasil yang sama adalah teorema Akra-Bazzi "Pada Solusi Persamaan Linier Linear", Optimalisasi Komputasi dan Aplikasi, 10 (2), 195-210 (1998), atau Drmota dan Szpankowski "Teorema Master untuk Diskrit Membagi dan Taklukkan Perulangan ", SODA'11 < dl.acm.org/citation.cfm?id=2133036.2133064 >.

vonbrand

Berikut tautan ke makalah di atas, yang tidak berada di belakang paywall.

Paresh

IIRC ini dibahas dalam CLRS bab 4.

Kaveh

@ Kaveh Terima kasih atas penunjuknya. Sebagian besar, mereka menyebutnya "kecerobohan yang bisa ditoleransi"; ini baik-baik saja dalam konteksnya, karena mereka menganggap Anda hanya memperoleh hipotesis, yang kemudian terbukti benar dengan induksi. Mereka menyebut bahayanya (4.6). Dalam 4.6.2 mereka memberikan bukti, tetapi tingkat tinggi dan mereka tidak secara eksplisit mengatakan apa pembatasan harus berada di tempat. Jadi sepertinya ada sesuatu seperti " sehingga matematika harus melalui", yang saya pikir terutama mengharuskan untuk memiliki "bagus" kelas- .

T

$T$

T

$T$

f

$f$

Θ

$\Theta$

Raphael

Dalam kasus umum ketika Anda tidak memiliki ukuran yang sama, Anda dapat menggunakan metode Akra-Bazzi yang merupakan generalisasi dari teorema master, yakin bagaimana mengubah fungsi spesifik ke sesuatu yang bekerja dalam teorema ini memerlukan sedikit trik, dan untuk sesuatu seperti penggabungan penggabungan, inilah yang biasanya digunakan orang untuk membuktikan kompleksitas waktu.

Sepanjang jawaban ini, kami menganggap dan adalah non-negatif. Bukti kami berfungsi kapan saja untuk beberapa monoton . Ini termasuk contoh Mergesort Anda, di mana , dan fungsi apa pun yang memiliki tingkat pertumbuhan polinomial (atau bahkan ). $f$ $T$ $f = \Theta(g)$ $g$ $f=\Theta(n)$ $\Theta(n^a \log^b n)$

Mari kita perhatikan dulu kasus bahwa adalah monoton non-menurun (kami akan mengendurkan asumsi ini nanti). Kami berkonsentrasi pada pengulangan sampel Anda Perulangan ini membutuhkan dua kasus dasar, dan . Kami membuat asumsi bahwa , yang juga akan kita bersantai nanti. $f$

T (n) = T (⌊ n / 2 ⌋) + T (⌈ n / 2 ⌉) + f (n) .

$T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + f(n).$

T (0)

$T(0)$

T (1)

$T(1)$

T (0) \leq T (1)

$T(0) \leq T(1)$

Saya mengklaim bahwa adalah monoton yang tidak berkurang. Kami membuktikan dengan induksi lengkap bahwa . Ini diberikan untuk , jadi mari . Kami memiliki Ini menyiratkan bahwa Jadi jika , kita selesai. Ini selalu terjadi jika solusi untuk kekuatan dua adalah dalam bentuk . $T(n)$ $T(n+1) \geq T(n)$ $n = 0$ $n \geq 1$

\begin{aligned} T (n + 1) & = T (⌊ (n + 1) / 2 ⌋) + T (⌈ (n + 1) / 2 ⌉) + f (n + 1) \\ \geq T (⌊ n / 2 ⌋) + T (⌈ n / 2 ⌉) + f (n) = T (n) . \end{aligned}

$\begin{align*} T(n+1) &= T(\lfloor (n+1)/2 \rfloor) + T(\lceil (n+1)/2 \rceil) + f(n+1) \\ &\geq T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + f(n) = T(n). \end{align*}$

T (2^{⌊ \log_{2} n ⌋}) \leq T (n) \leq T (2^{⌈ \log_{2} n ⌋}) .

$T(2^{\lfloor \log_2 n \rfloor}) \leq T(n) \leq T(2^{\lceil \log_2 n \rfloor}).$

T (2^{m}) = Θ (T (2^{m + 1}))

$T(2^m) = \Theta(T(2^{m+1}))$

T (n) = Θ (n^{a} \log^{b} n)

$T(n) = \Theta(n^a \log^b n)$

Sekarang mari kita santai dengan asumsi bahwa . Pertimbangkan rekurensi baru didefinisikan dengan cara yang persis sama, hanya . Kita dapat membuktikan dengan induksi bahwa . Demikian pula, kita dapat mendefinisikan perulangan baru memuaskan , dan kemudian . Dengan menggunakan teorema Master, kita melihat bahwa dan untuk fungsi yang sama , dan juga juga. $T(0) \leq T(1)$ $T'$ $T'(0) = T'(1) = \min(T(0),T(1))$ $T'(n) \leq T(n)$ $T''$ $T''(0) = T''(1) = \max(T(0),T(1))$ $T(n) \leq T''(n)$ $T'=\Theta(h)$ $T''=\Theta(h)$ $h$ $T = \Theta(h)$

Sekarang mari kita santai dengan asumsi bahwa adalah monoton. Misalkan untuk beberapa fungsi monoton . Jadi untuk beberapa dan cukup besar. Kami berasumsi untuk kesederhanaan bahwa ; kasus umum dapat ditangani seperti pada paragraf sebelumnya. Sekali lagi kita mendefinisikan dua rekurensi dengan mengganti dengan (masing-masing). Sekali lagi teorema Master akan memberikan hasil yang sama (hingga kelipatan konstan), yang juga identik (hingga kelipatan konstan) dengan apa yang akan kita dapatkan dengan menyelesaikan perulangan asli hanya pada kekuatan dua. $f$ $f = \Theta(g)$ $g$ $cg(n) \leq f(n) \leq Cg(n)$ $c,C>0$ $n$ $n=0$ $T',T''$ $f$ $cg,Cg$

Yuval Filmus
sumber

Akhirnya harus membaca ini lebih cermat. Terima kasih banyak! Saya pikir saya akan mencatat ini untuk pembaca masa depan (karena saya tersandung tentang hal itu): bukan pembatasan karena itu hanya salah untuk super-polinomial dan teorema Master tidak berlaku untuk itu.

T (2^{m}) \in Θ (T (2^{m + 1}))

$T(2^m) \in \Theta(T(2^{m+1}))$

T

$T$

Raphael

Saya telah mencoba menuliskan bukti Anda lebih terinci dan terjebak membuktikan kalimat terakhir Anda, "yang juga identik (...) dengan apa yang akan kita dapatkan dengan menyelesaikan perulangan asli hanya pada kekuatan dua." Secara khusus, kita harus menunjukkan bahwa kita berakhir dalam kasus yang sama dari teorema Master untuk , dan . Ini bukan masalah untuk kasus 1 dan 2, tapi saya tidak bisa menunjukkan keberadaan untuk kasus 3 (lihat versi di CLRS, p94 di edisi ke-3). Apakah Anda memikirkan hal itu, atau apakah Anda bekerja dengan versi yang mirip dengan versi Wikipedia ?

c g

$cg$

f

$f$

C g

$Cg$

c < 1

$c < 1$

Raphael

Ini teknis. Jika maka masalahnya hilang, lihat misalnya users.encs.concordia.ca/~chvatal/notes/master.pdf . Fungsi akan secara otomatis memenuhi persyaratan. Saya membayangkan hal yang sama berlaku untuk dan seterusnya. Atau, sebutkan saja kondisi ini langsung pada daripada pada : harus ada beberapa "biasa" memuaskan .

f = Θ (n^{α})

$f = \Theta(n^\alpha)$

g

$g$

f = Θ (n^{α} \log^{β} n)

$f = \Theta(n^\alpha \log^\beta n)$

g

$g$

f

$f$

g

$g$

f = Θ (g)

$f = \Theta(g)$

Yuval Filmus

Nah, Anda mengklaim " monoton" adalah kondisi yang cukup (dan saya percaya Anda) jadi saya mencoba untuk bekerja dengan itu. Teorema Master seperti yang diberikan dalam misalnya CLRS berlaku untuk misalnya , jika saya tidak salah, jadi pembatasan untuk fungsi polylogarithmic atau semacam itu tidak "teknis" tetapi melemahkan hasilnya dengan baik. Mengangkat "keteraturan" ke tidak membantu, omong-omong: Saya sudah memilikinya dalam kasus penting melalui keteraturan / (dengan asumsi). Jadi saya kembali pada komentar saya sebelumnya, sayangnya. Jika ini benar-benar hanya teknis, saya tidak melihatnya. Terlalu banyak ketidaksetaraan.

g

$g$

f : n \mapsto 2^{n}

$f : n \mapsto 2^n$

g

$g$

c g

$cg$

C g

$Cg$

Raphael

Saya masih berpikir itu teknis. Kondisi yang Anda khawatirkan adalah kondisi teknis. Untuk sebagian besar fungsi yang muncul dalam praktik, kondisi akan berlaku. Anda meminta kondisi paling umum untuk sketsa bukti di atas. Itu pertanyaan menarik yang terlalu malas saya jawab.

Yuval Filmus

Bukti yang kuat untuk validitas asumsi

Jawaban: