Memecahkan T (n) = 2T (n / 2) + log n dengan metode pengulangan

Saya sedang memecahkan hubungan pengulangan. Hubungan perulangan pertama adalah

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

Solusi yang satu ini dapat ditemukan oleh Master Theorem atau metode pengulangan pohon. Pohon perulangan akan seperti ini:

Solusinya adalah:

$T(n)=\underbrace{n+n+n+...+n}_{\log_2{n}=k \text{ times}}=\Theta(n \log{n})$

Selanjutnya saya menghadapi masalah berikut:

$T(n)=2T(n/2)+\log{n}$

Buku saya menunjukkan bahwa dengan teorema master atau bahkan dengan beberapa pendekatan substitusi, perulangan ini memiliki solusi $\Theta(n)$ . Ini memiliki struktur yang sama seperti pohon di atas dengan satu-satunya perbedaan yang pada setiap panggilan melakukan $\log{n}$ bekerja. Namun saya tidak dapat menggunakan pendekatan di atas yang sama untuk masalah ini.

Istilah non-rekursif dari hubungan perulangan adalah pekerjaan untuk menggabungkan solusi dari subproblem. Level dari pohon perulangan (biner) Anda mengandung subproblem dengan ukuran , jadi Anda harus terlebih dahulu menemukan pekerjaan total pada level dan kemudian meringkas pekerjaan ini pada semua tingkat pohon.$k$$2^k$$\frac {n}{2^k}$$k$

Misalnya, jika pekerjaannya adalah konstan , maka total pekerjaan pada level akan menjadi , dan total waktu akan diberikan dengan jumlah berikut:$C$$k$$2^k \cdot C$$T(n)$

$$T(n) = \sum_{k=1}^{\log_2{n}}2^k C = C(2^{\log_2{n}+1}-2) = \Theta(n)$$

Namun, jika pekerjaan tumbuh secara logaritmik dengan ukuran masalah Anda harus menghitung solusi secara akurat. Serialnya akan seperti berikut:

$$T(n)=\log_2{n}+\underbrace{2\log_2(\frac {n} {2})+4\log_2(\frac {n} {4})+8\log_2(\frac {n} {8}) + ....}_{\log_2{n} \text{ times}}$$

Ini akan menjadi jumlah yang cukup kompleks:

$$T(n)=\log_2{n}+\sum_{k=1}^{\log_2{n}}2^k \log_2(\frac {n} {2^k})$$

Saya akan sementara menunjukkan dan menyederhanakan penjumlahan di atas:$m=\log_2{n}$

$$\sum_{k=1}^{m}2^k \log_2(\frac {n} {2^k})=\\=\sum_{k=1}^{m}2^k(\log_2{n}-k)=\\=\log_2{n}\sum_{k=1}^{m}2^k-\sum_{k=1}^{m}k2^k=\\=\log_2{n}(2^{m+1}-2)-(m2^{m+1}-2^{m+1}+2)$$

Di sini saya menggunakan rumus untuk jumlah dari kalkulator aljabar simbolik online Wolfram | Alpha . Maka kita perlu mengganti kembali dengan :$\sum_{k=1}^{m}k2^k$$m$$\log_2{n}$

$$T(n)=\log_2{n}+2n\log_2{n}-2\log_2{n}-2n\log_2{n}+2n-2$$ $$=2n-\log_2{n}-2=\Theta(n)$$

QED