Memecahkan relasi yang berulang

Saya ingin membuktikan bahwa kompleksitas waktu dari suatu algoritma adalah polylogarithmic dalam skala input.

Relasi pengulangan dari algoritma ini adalah , di mana .$T(2n) \leq T(n) + T(n^a)$$a\in(0,1)$

Tampaknya untuk beberapa tergantung pada . Tapi saya tidak bisa membuktikan ketidaksetaraan ini. Bagaimana mengatasi hubungan pengulangan ini?$T(n) \leq \log^{\beta}{n}$$\beta$$a$

Saya hanya ingin mendapatkan polylogarithmic batas atas di n.

Dugaan Anda salah. Bahkan, tidak sulit untuk menunjukkan asumsi itu$T(n) > 0$ untuk semua $n > 0$, kemudian $T(n) = \Omega(\log^k n)$untuk semua $k$. Memang, untuk menahan ini kita perlu itu cukup besar$n$ kami akan memiliki

$$(1+a^k) \log^k n = \log^k n + \log^k n^a \geq \log^k (2n),$$ atau $\sqrt[k]{1+a^k} \log n \geq \log n + \log 2$, yang berlaku selama $[\sqrt[k]{1+a^k}-1]\log n \geq \log 2$, dan khususnya untuk yang cukup besar $n$.

Apa urutan pertumbuhan yang benar $T(n)$? Untuk mencoba dan mencari tahu, tulis$S(n) = T(2^n)$. Perulangan sekarang menjadi

$$S(n+1) = S(n) + S(an).$$ Untuk yang besar $n$, kami harapkan $S(n+1) - S(n)$ menjadi sangat dekat $S'(n)$, dan secara heuristik kita harapkan itu $S$ memuaskan $S'(n) = S(an)$. Persamaan ini tampaknya agak sulit untuk dipecahkan, tetapi solusi perkiraannya adalah$S(n) = n^{\Theta(\log n)}$. Mengganti kembali, kami menyimpulkan bahwa urutan pertumbuhan$T(n)$ harus seperti $(\log n)^{\Theta(\log \log n)}$.