$ T(n)= T(\log n)+ \mathcal O(1) $ Relación de recurrencia

Question

¿Cuál es la solución de la siguiente relación de recurrencia? $$ \begin{align} T(1) &= 1\\ T(n) &= T(\log n) + \mathcal O(1) \end {align} $$

una) $O(log n)$

b)$ O (log^* n) $

c)$ O (log^2 n) $

d)$ O (n / log n) $

Answer 1

Me gusta pensar de recurrencia de la forma $T(n) = T(f(n)) + \Theta(1)$^† como "acumulador" de las recurrencias. Esto es debido a que "suman" el número de iteraciones--o algún múltiplo de la misma-se necesita para $f(n)$ a ir más allá de algún límite.

En palabras, esta recurrencia es determinar el número de veces que se debe tomar un logaritmo antes de llegar a $1$. Esto debe sonar familiar a un estudiante de informática, ya que hay una función especial para describir este número!

Esta función especial se $\lg^*n$, que es el logaritmo iterado. Ya que algunos pueden no estar familiarizados con esta función, se define como: $$\lg^*n:=\begin{cases} 0& n\leq 1\\ 1+\lg^*(\lg(n)) & n > 1 \end{casos}$$

Así, una buena conjetura sería que $T(n) \in \Theta(\lg^*n)$. (De hecho, si tuviéramos $+1$ en lugar de $+\Theta(1)$, la solución exacta sería: $T(n) = \lg^* n + 1$.) La conjetura puede ser probado algo fácilmente con fuerte inducción.

---

^†Tengo que hacer una distinción importante: si usted está realmente hablando de big-$\mathcal O$ la notación, no hay una única "respuesta correcta" a esta pregunta. Esto es debido a que $\mathcal O(\cdot )$ es un límite superior para el comportamiento asintótico de la repetición, más que apretada obligado. La gente suele confundir $\mathcal O(\cdot)$$\Theta(\cdot)$. Como tal, estoy asumiendo que usted significó $\Theta(\cdot)$ dondequiera que usted escribió $\mathcal O(\cdot)$.

Answer 2

La mejor manera que sé cómo hacerlo, es para resolver por adivinar inductivo y prueba. Por ejemplo, ya estás preguntando si la función es $\mathcal{O}(log(n))$.

$T(n) \in \mathcal{O}(f(n))$ si existen constantes $c$, $n_0>0$ tal que $T(n) \leq cf(n))$ todos los $n >n_0$.

Voy a reemplazar el $O(1)$ con 1 (usted puede hacer esto con un sin especificar constante). Así que voy a asumir registro de la base 2, y voy a afirmar que $T(n) \leq 2lg(n)$. Mi $n_0 =2$. $T(2) = T(1)+ 1 = 2 \leq 2lg(2) =2$ sostiene. Asumir que esto tiene para todos los $n'< n$ Entonces (retrocediendo): $T(n) = T(lg(n))+1 \leq 2lg(lg(n))+1= 2lg(lg(n) \sqrt{2})$. Ahora tenemos que mostrarle $lg(n) \sqrt{2} \leq n$ (es).

Otra forma de resolver es resolver desenrollando: a Partir de $n$, ¿cuántas veces se puede tomar el registro hasta llegar a 1? Acerca de $log(n)$ veces. Escribir la suma de lo que va a suceder en cada paso, y te aviso que recibirá una suma de una constante $log(n)$ veces. Yo todavía iba a utilizar la perspectiva de la prueba para demostrar que es cierto.

También, hay el maestro teorema, pero no estaba seguro de cómo se aplica en este caso.