Recurrencia - Teorema maestro - Cuestión asintótica

Question

Lo siento si esta pregunta se ha hecho antes, pero estoy tratando de averiguar esto. Estoy usando el texto CLRS, Introducción a los Algoritmos. En el capítulo Recurrencias, en la sección Teorema Maestro, se da el siguiente ejemplo con la solución:

$$T(n) = 3T\left(\frac{n}4\right) + n\log n $$

Toma,

$$ a = 3, b =4, f(n) = n\log n $$

Utilizando el método Maestro, dice

$$f(n) = \Omega(n^{\log_4 3 + \epsilon}) $$

No entiendo cómo $f(n)$ se "suponía" que tenía este límite inferior ( $\Omega$ ). Agradecería enormemente a cualquiera que me indicara por qué es así.

Si se necesitan más detalles para entender el problema, por favor hágamelo saber. Añadiré más detalles a esta pregunta.

TIA,

Jake Clawson

EDIT: Doy las gracias a todos los que han respondido a continuación. He respondido a cada uno por separado. Pero mi pregunta sigue en pie. El libro dice directamente que $f(n)$ es $\Omega$ . No entiendo esto y esta es la clave para aplicar el Teorema Maestro porque una vez que $f(n)$ se sabe qué caso aplicar.

Answer 1

Así que quiere entender por qué $n\log n=\Omega(n^{\log_4 3+\epsilon})$

La forma más sencilla es mirar el límite

$\lim_{n->\infty}\frac{n\log n}{n^c}$

que se evalúa a

$\lim_{n->\infty}\frac{\log n+1}{cn^{c-1}}$ donde $c=log_4 3+\epsilon$

desde $\log_4 3\lt1$ existe $\epsilon\gt0$ tal que $\log_4 3+\epsilon=c\lt1$ . Por lo tanto, el límite tendería a $\infty$ y por lo tanto $nlogn=\Omega(n^{\log_43+\epsilon})$

Answer 2

Bueno, en realidad, el hecho que usted afirma no es tan interesante.

1. Si $G(n)$ satisface $G(n) = 3G(n/4)$ entonces claramente, $G(n) < T(n)$ (para la misma condición límite). Como se deduce del teorema maestro, o comprobar fácilmente usted mismo, $G(n) = A \, n^{\log_4{3}} + B$ .

2. $T(n)$ es seguramente $> n\, \log n$ . Porque $\log_4{3} < 1$ , $n^{\log_4{3}} = o(n) = o(n\, \log n)$ . Así que $T(n)$ es $\omega(n) = \omega(n^{\log_4{3}+\epsilon})$ para algún épsilon positivo pequeño.

Answer 3

El teorema de Master trata de recurrencias de la forma

$$T(n) = aT(n/b) + f(n)$$

El teorema se divide en tres casos, según el comportamiento de $f(n)$ "relativo" a $n^{\log_b a}$

Caso 2) $f(n) = \Theta(n^{\log_b a})$

Caso 1) $f(n) = \mathcal{O}(n^{\log_b a - \epsilon})$

Caso 3) $f(n) = \Omega(n^{\log_b a + \epsilon})$

En tu caso, $f(n) = n\log n$ , $a = 3$ , $b=4$ .

Para aplicar el Master necesitamos $f(n)$ para caber en una de esas maletas.

Ahora $\log_4(3) \lt \log_4 4 = 1$ .

Así pues, podemos eliminar los casos 1) y 2).

Lo que queda es el caso 3), y podemos aplicarlo, eligiendo $\epsilon = 1 - \log_4 3$ porque $n \log n = \Omega(n) = \Omega(n^{\log_4 3 + (1- \log_4 3)})$ .

Answer 4

Toma $c=\lg\left(n_{0}\right)$ en la siguiente definición del $\Omega$ -notación:

$$ \Omega\left(g\left(n\right)\right)=\left\{ f\left(n\right):\exists\left(c>0\wedge n_{0}>0\right)\backepsilon0\leq cg\left(n\right)\leq f\left(n\right)\forall n\geq n_{0}\right\} $$

que aparece en la página 48 de la tercera edición del libro. Así, con $g\left(n\right)=n$ para $n\geq n_{0}$ tenemos que

$$ n\lg\left(n_{0}\right)\leq n\lg\left(n\right) $$

Esto demuestra que $f\left(n\right)=\Omega\left(n\right)$ que responde a a la pregunta.