Qu'est-ce que la partie supérieure et la limite inférieure pour $T(n) = T(\sqrt{n}) +3$, en supposant que $T(n)$ est une constante pour $n\leq 10$

Question

En déroulant la récursivité, \begin{equation*} \begin{split} T(n) &= T(\sqrt{n}) + 3 = T(n^{\frac{1}{2}}) + 3 \\ &= (T(n^{\frac{1}{4}})+3) +3 = T(n^{\frac{1}{4}}) +6 \\ &= (T(n^{\frac{1}{8}})+3) + 6 = T(n^{\frac{1}{8}}) +9 \\ \end{split} \end{equation*}

Réclamation: $T(n) = T(n^{\frac{1}{2^k}}) + 3 \cdot k$

Cas De Base: $k=1$ \begin{equation*} \begin{split} T(n) &= T(n^{\frac{1}{2^1}}) + 3 \cdot 1 \\ T(n) &= T(\sqrt{n}) + 3 \end{split} \end{equation*}

Inductive Hypothèse:Supposons que k=i est vrai, \begin{equation*} \begin{split} T(n) &= T(n^{\frac{1}{2^i}}) + 3 \cdot i \\ &= (T(n^{\frac{1}{2^j'+1}}+3) + 3 \cdot i \\ &= (T(n^{\frac{1}{2^i+1}}) + 3 \cdot (i +1) \\ \end{split} \end{equation*}

Ce sont mes questions...

1. Je ne suis pas sûr si mon hypothèse de base est correct
2. Je suis également pas sûr de savoir comment procéder (quelle valeur puis-je remplacer pour obtenir une forme fermée)

Toute aide serait appréciée!

Answer 1

Où en êtes-vous à l'aide de T(n) = c pour n <= 10?Votre formule est mal lorsque l'argument est inférieur à 10.K = 1 n'est pas le cas de base.N <= 10 est le cas de base.

Clairement T(n) = c pour n <= 10, T(n) = c+3 si 10 < n <= 100, T(n) = c+6 si 100 < n <= De 10 000, T(n) = c+9 si de 10 000 < n <= 100 000 000 d'etc.

Soit f(n) = log_10 (max (n, 10)) donc, pour les quatre cas ci-dessus, nous avons f(n) = 1, 1 < f(n) <= 2, 2 < f(n) <= 4, 4 < f(n) <= 8 etc.

Soit g(n) = ceil(log_2(f(n))), alors g(n) = 0, 1, 2, 3, etc, et T(n) = c + 3 g(n).

Answer 2

Supposons ce qui suit: $T(n) \leq c\log_2(\log_2(n)), n > 10$ et $T(4) = c$ comme une base de cas (parce que $4^2 > 10$.)

Maintenant, nous pouvons procéder par induction:
Cas de Base: $$c\log_2(\log_2(4)) = c\log_2(2) = c \geq T(4)$$ Cas général:
Nous savons $T(\sqrt{n}) \leq c\log_2(\log_2(\sqrt{n}))$ (induction de l'hypo.).Donc:

$$T(n) = T(\sqrt{n})+3 \leq c\log_2(\log_2(\sqrt{n})) + 3$$

Nous pouvons réécrire le bon terme:$$c\log_2(\log_2(\sqrt{n})) + 3 = c\log_2\left(\frac 12 \log_2(n) ight) +3 = c\log_2(\log_2(n)) - c + 3$$ Laissez $c = 3$.Il en résulte:$$T(n) = T(\sqrt{n})+3 \leq 3\log_2(\log_2(n)) - 3 + 3 = 3\log_2(\log_2(n))$$ Donc:$T(n) \leq 3\log_2(\log_2(n))$.

---

Vous pouvez également afficher $T(n) \geq 3\log_2(\log_2(n))$ de la même manière.Ainsi $T(n)\O(\log \log(n))$.J'espère que cette aide.