Lösen der Wiederholungsrelation

Ich möchte beweisen, dass die zeitliche Komplexität eines Algorithmus in der Eingabeskala polylogarithmisch ist.

Die Wiederholungsrelation dieses Algorithmus ist , wobei a ∈ ( 0 , 1 ) ist .$T(2n) \leq T(n) + T(n^a)$$a\in(0,1)$

Es scheint, dass für einige β von a abhängt . Aber ich kann diese Ungleichheit nicht beweisen. Wie kann man diese Wiederholungsbeziehung lösen?$T(n) \leq \log^{\beta}{n}$$\beta$$a$

Ich möchte nur eine obere Grenze des Polylogarithmus in n erhalten.

$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$und insbesondere für groß genug $n$.

Was ist die richtige Reihenfolge des Wachstums von $T(n)$? Um es herauszufinden, schreiben Sie$S(n) = T(2^n)$. Die Wiederholung wird jetzt

$$S(n+1) = S(n) + S(an).$$ Für große $n$, Wir würden erwarten $S(n+1) - S(n)$ sehr nahe sein $S'(n)$und so heuristisch würden wir das erwarten $S$ erfüllen $S'(n) = S(an)$. Diese Gleichung scheint etwas schwer zu lösen, aber eine ungefähre Lösung ist$S(n) = n^{\Theta(\log n)}$. Wenn wir zurücksetzen, schließen wir, dass die Reihenfolge des Wachstums von$T(n)$ sollte so etwas sein $(\log n)^{\Theta(\log \log n)}$.