Résolution de la relation de récurrence

Je veux prouver que la complexité temporelle d'un algorithme est polylogarithmique dans l'échelle d'entrée.

La relation de récurrence de cet algorithme est , où .$T(2n) \leq T(n) + T(n^a)$$a\in(0,1)$

Il semble que pour certains dépend de . Mais je ne peux pas prouver cette inégalité. Comment résoudre cette relation de récurrence?$T(n) \leq \log^{\beta}{n}$$\beta$$a$

Je veux juste obtenir une polylogarithmique de borne supérieure dans n.

Votre supposition est fausse. En fait, il n'est pas difficile de montrer qu'en supposant pour tout , alors pour tout . En effet, pour que cela tienne, nous avons besoin que pour assez grand, nous aurions ou , qui dure aussi longtemps que , et en particulier pour assez grand .$T(n) > 0$$n > 0$$T(n) = \Omega(\log^k n)$ $k$$n$

$$(1+a^k) \log^k n = \log^k n + \log^k n^a \geq \log^k (2n),$$ $\sqrt[k]{1+a^k} \log n \geq \log n + \log 2$$[\sqrt[k]{1+a^k}-1]\log n \geq \log 2$$n$

Quel est l'ordre de croissance correct de ? Pour essayer de le savoir, écrivez . La récurrence devient alors Pour les grands , nous nous attendrions à ce que soit très proche de , et donc heuristiquement nous nous attendrions à ce que satisfasse . Cette équation semble un peu difficile à résoudre, mais une solution approximative est . En substituant en arrière, nous déduisons que l'ordre de croissance de devrait être quelque chose comme .$T(n)$$S(n) = T(2^n)$

$$S(n+1) = S(n) + S(an).$$ $n$$S(n+1) - S(n)$$S'(n)$$S$$S'(n) = S(an)$$S(n) = n^{\Theta(\log n)}$$T(n)$$(\log n)^{\Theta(\log \log n)}$