¿Cuál es la solución a la siguiente relación de recurrencia con raíz cuadrada: $T(n)=T (\sqrt{n}) + 1$?

Question

Esta parece una pregunta anterior, pero no lo es.

$$T(n)=\begin{cases} T (\sqrt{n}) + 1 \quad & \text{ if } n>1 \\ 1 & \text{ if }n=1\end{casos}$$

Mi profesor me dio esto en la clase de ayer. Esto es donde estoy atascado:

$$T(n) = T(n^{1/2})+1 = T(n^{1/4})+2 = T(n^{1/8})+3 = \dots = T(n^{1/ 2 ^k})+k$$

Ahora esto va a continuar hasta que

$$n^{1/ 2 ^k}=1$$

¿Cómo debo proceder por delante? Si me registro en ambos lados, luego RHS se convierte en cero. ¿Cómo resolver la relación?

No quiero usar el teorema Maestro, quiero saber de dónde y por qué estoy atascado.

Answer 1

Tenemos una recurrencia que es ostensiblemente más de los números enteros. Pero si $n$ es un número entero, entonces $\sqrt{n}$ no es necesariamente un entero. Una forma de conseguir una informal respuesta es imaginar que empezamos con un entero $n$ de la forma $2^{2^m}$. A continuación,$\sqrt{n}=2^{2^{m-1}}$. (Para encontrar la raíz cuadrada, se divide el exponente por $2$.)

Así subiendo de a$2^{2^0}$$2^{2^m}$, se ha incrementado $T$$m$. Si empezamos con $T(2)=0$, luego $$T\left(2^{2^m}\right)=m.$$ Si $T(2)$ tiene algún otro valor $a$,$T\left(2^{2^m}\right)=a+m$. Tenga en cuenta que $m=\log_2\left(\log_2\left(2^{2^m}\right)\right).$ Así que para este valor de $n$, e $T(2)=0$,$T(n)=\log_2(\log_2(n))$. Si $T(2)=a$, sólo tiene que añadir $a$.

Nota: El cálculo anterior puede llevarse a cabo básicamente de la misma manera, si suponemos que $T(n)=T(\lfloor\sqrt{n}\rfloor)+1$. La conclusión es que para la gran $n$, $T(n)$ se comporta como $\lg\lg n$. Y $\lg\lg n$ crece glacial lentamente.

Answer 2

En primer lugar, este pertenece a una recurrencia de la relación de la forma http://eqworld.ipmnet.ru/en/solutions/fe/fe2308.pdf

Vamos $n_1=\ln n$ , $T_1(n_1)=T(n)$ ,

A continuación, $T_1(n_1)=T_1\left(\dfrac{n_1}{2}\right)+1$

Entonces, este pertenece a una recurrencia de la relación de la forma http://eqworld.ipmnet.ru/en/solutions/fe/fe2303.pdf

Vamos $n_2=\ln n_1$ , $T_2(n_2)=T_1(n_1)$ ,

A continuación, $T_2(n_2)=T_2(n_2-\ln2)+1$

De hecho, este pertenece a una recurrencia de la relación de la forma http://eqworld.ipmnet.ru/en/solutions/fe/fe1108.pdf.

La solución general de esta relación de recurrencia es $T_2(n_2)=\Theta(n_2)+T_{2,p}(n_2)$ donde $\Theta(n_2)$ es arbitraria función periódica con período de $\ln2$

Por suerte podemos encontrar $T_{2,p}(n_2)$ por el método de coeficientes indeterminados:

Deje $T_{2,p}(n_2)=An_2$ ,

A continuación, $T_{2,p}(n_2-\ln2)=A(n_2-\ln2)$

$\therefore An_2-A(n_2-\ln2)\equiv1$

$A\ln2\equiv1$

$\therefore A\ln2=1$

$A=\dfrac{1}{\ln2}$

$\therefore T_2(n_2)=\Theta(n_2)+\dfrac{n_2}{\ln2}$ donde $\Theta(n_2)$ es arbitraria función periódica con período de $\ln2$

$T(n)=\Theta(\ln\ln n)+\dfrac{\ln\ln n}{\ln2}=\Theta(\ln\ln n)+\log_2\ln n$ donde $\Theta(n)$ es arbitraria función periódica con período de $\ln2$

Tenga en cuenta que $n$ directamente no se puede sustituir $1$ como la recursividad no puede formar al $n=1$ .

Answer 3

Vamos a encontrar las funciones de $x\mapsto T(x)$, definida para todo real $x>1$, que satisfacen el dado de la recurrencia de la relación.

Reemplace la función desconocida $T$ por $$g(\alpha):=T\bigl(\exp(2^\alpha)\bigr)\qquad(-\infty<\alpha<\infty)\ .$$ Entonces, de acuerdo a la relación de recurrencia para $T$, la función de $g$ satisface $$g(\alpha)=T\bigl(\sqrt{\exp(2^\alpha)}\bigr)+1=T\bigl(\exp(2^{\alpha-1})\bigr)+1=g(\alpha-1)+1\ ,$$ o $$f(\alpha):=g(\alpha)-\alpha=g(\alpha-1)-(\alpha-1)=f(\alpha-1)\qquad(\alpha\in{\mathbb R})\ .$$ Esto demuestra que $$g(\alpha)=\alpha +f(\alpha)\ ,$$ donde ahora se $f$ es una función arbitraria de plazo,$1$.

Con el fin de devolver a la variable $x$ tenemos que resolver la ecuación de $\exp(2^\alpha)=x$$\alpha$, y obtener un $\alpha={\log\log x\over\log 2}$. Como los pasos que conducen a $g$ puede ser revertida, se sigue que $$T(x)=g\Bigl({\log\log x\over\log 2}\Bigr)={\log\log x\over\log 2}+ f\Bigl({\log\log x\over\log 2}\Bigr)\qquad(x>1)$$ es la solución de nuestro problema.

Answer 4

Si usted se está preguntando por el comportamiento asintótico de la secuencia de $\langle T(n):n\in\Bbb Z^+\rangle$, véase André respuesta. Si usted está buscando para una exacta la forma cerrada de la solución, tendrás que hacer algún ajuste en la recurrencia a reemplazar a $\sqrt n$ por un número entero. Como un ejemplo, usted podría suponer que hay una implícita la función del suelo en la recurrencia: $T(n)=T(\lfloor\sqrt n\rfloor)$$n>1$. Ahora supongamos que $m^2\le n<(m+1)^2$ para algún entero positivo $m$; a continuación,$m\le\sqrt n<m+1$, lo $\lfloor\sqrt n\rfloor=m$, e $T(n)=T(m)+1$. Esto significa que $T$ será constante a lo largo de todo el intervalo de $\left[m^2,(m+1)^2\right)$.

Ahora a hacer un poco de tabla:

$$\begin{array}{r|cc} m&1&&&2&&&&&3&&&&&&&4\\ \hline n&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16\\ \hline T(n)&1&2&2&3&3&3&3&3&4&4&4&4&4&4&4&5 \end{array}$$

Esto debe darle una muy buena idea de lo $T$ lo hace bajo las hipótesis, pero lo voy a dejar a usted para traducir ese comportamiento en una fórmula concreta.