¿Cómo puedo resolver la recurrencia $$T (n) = T \left(\frac{n}{2} +\sqrt{n}\right) +\sqrt{6046}\ ?$$
Por favor, no se limite a escribir el nombre del método, como acabo de empezar a aprender estas cosas y las cosas son un poco difícil para mí para averiguar por mi cuenta.
Gracias de antemano.
Creo Akra-Bazzi funciona para este y el te $T(x) = \theta(\log x)$.
La recurrencia tiene satisface los supuestos de Akra-Bazzi y llegamos $p=0$ (echa un vistazo a la wiki para lo $p$ es). $p=0$ implica $T(x) = \theta(\log x)$ en este caso (como $g(x)$ es constante).
Una más elementales de la prueba consisten en mostrar a $T(x) = \mathcal{O}(\log x)$ como en el de Ross en la respuesta, a continuación, tratar de mostrar a $T(x) = \Omega(\log x)$.
Aquí está una explicación de la aplicación de Akra-Bazzi a esta.
Akra-Bazzi se utiliza para resolver las recurrencias de la forma:
$$ T(x) = g(x) + \sum_{i=1}^{m} a_i T(b_i x + h_i(x)) \ \text{where}\ x > x_0 $$
donde $x$ es la variable, $a_i, b_i$ son constantes.
En tu caso, tenemos que
$$T(x) = \sqrt{6046} + T(0.5 x + \sqrt{x})$$
Observe que, esto corresponde a $\displaystyle m=1$.
Las suposiciones hechas por el teorema de son
1) $\displaystyle a_i \gt 0$. Esto es cierto en su caso, como $\displaystyle a_1 = 1$.
2) $\displaystyle 0 \lt b_i \lt 1$. Esto es cierto en su caso, como $\displaystyle b_1 = 0.5$.
3) $\displaystyle |g(x)| = \mathcal{O}(x^c)$ algunos $c$. En nuestro caso $\displaystyle g(x) = \sqrt{6046}$ es constante.
4) $h_i(x) = \mathcal{O}(\frac{x}{\log^2 x})$. En nuestro caso $h_1(x) = \sqrt{x} = \mathcal{O}(\frac{x}{\log^2 x})$ $\displaystyle \log^2 x \le K \sqrt{x}$ para suficientemente grande $\displaystyle x$.
Hay un par más, pero son triviales para verificar.
Ahora para aplicar Akra-Bazzi teorema, usted necesita encontrar a $\displaystyle p$ tal que $\displaystyle \sum_{i=1}^{m} a_i (b_i)^p = 1$.
En nuestro caso, obtenemos $\displaystyle 0.5^p = 1$$\displaystyle p = 0$.
Una vez que nos encontramos con $\displaystyle p$, por el Akra-Bazzi teorema tenemos que
$$T(x) = \theta\left(x^p \left( 1 + \int_{1}^{x} \frac{g(t)}{t^{p+1}} \ \text{dt}\right)\right)$$
Desde $\displaystyle p = 0$ $\displaystyle g(t)$ es constante, tenemos que
$$T(x) = \theta\left(1 + \int_{1}^{x} \frac{\sqrt{6046}}{t} \ \text{dt}\right) = \theta(\log x)$$
También sugiero intentar completar la primaria prueba de que $\displaystyle T(x) = \Omega(\log x)$. La relación $\displaystyle T(x) \leq T(2x/3) + 80$, sólo muestra que la $\displaystyle T(x) = \mathcal{O}(\log x)$.
La declaración de $\displaystyle T(x) = \theta(\log x)$ es más fuerte. Por ejemplo, $\displaystyle T(x) = 10$ también satisifies $\displaystyle T(x) \leq T(2x/3) + 80$, pero no va a satisfacer el original de su recurrencia.
Espero que ayude.
Usted puede obtener preciso asymptotics el uso de $f(n)=n/2 \leq n/2 + \sqrt{n} \leq n/2 + \sqrt{n} + 1/2 = g(n)$. Recorre de $f(n)$ $g(n)$ tiene una forma cerrada.
Las fórmulas para $f^k$ $g^k$ (k-ésimos itera) implica que el número de iteraciones de $h(x)=x/2 + \sqrt{x}$ necesaria para llevar a $n > 4$ abajo en cualquier intervalo de $[0,C]$$C>4$$\log_2{n} + O(1)$.
A partir de la recurrencia, $T(n)$ aumenta por $\sqrt{6046}$ en cada iteración, por lo que el asymptotics se $T(n) = \sqrt{6046} \log_2(n) + O(1)$.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
