Artículos

2.4: Resolver relaciones de recurrencia

2.4: Resolver relaciones de recurrencia



We are searching data for your request:

Forums and discussions:
Manuals and reference books:
Data from registers:
Wait the end of the search in all databases.
Upon completion, a link will appear to access the found materials.

Ejemplo ( PageIndex {1} )

Encuentre una relación de recurrencia y condiciones iniciales para (1, 5, 17, 53, 161, 485 ldots text {.} )

Solución

Encontrar la relación de recurrencia sería más fácil si tuviéramos algún contexto para el problema (como la Torre de Hanoi, por ejemplo). Por desgracia, solo tenemos la secuencia. Recuerde, la relación de recurrencia le dice cómo pasar de términos anteriores a términos futuros. ¿Que esta pasando aqui? Podríamos observar las diferencias entre los términos: (4, 12, 36, 108, ldots text {.} ) Observe que estos están creciendo en un factor de 3. ¿Es también la secuencia original? (1 cdot 3 = 3 text {,} ) (5 cdot 3 = 15 text {,} ) (17 cdot 3 = 51 ) y así sucesivamente. Parece que siempre terminamos con 2 menos que el siguiente período. ¡Ajá!

Entonces (a_n = 3a_ {n-1} + 2 ) es nuestra relación de recurrencia y la condición inicial es (a_0 = 1 text {.} )


Relaciones de recurrencia

A relación de recurrencia es una ecuación en la que cada término de la secuencia se define como una función de los términos anteriores.

Hay diferentes formas de resolver estas relaciones, vamos a examinar:

Resolver relaciones de recurrencia mediante derivación / sustitución repetida

La premisa para este tipo de solución es sustituir continuamente la relación de recurrencia en el lado derecho (es decir, sustituir un valor en la ecuación original y luego derivar una versión anterior de la ecuación). Las diversas derivaciones deben conducir a una forma generalizada de la ecuación que se puede resolver para una restricción de tiempo en el algoritmo / ecuación: Por ejemplo:

La única sustitución disponible en este punto es sustituir n / 2 por n en la ecuación original:

Suma c a ambos lados para derivar la ecuación original:

Ahora que se ha derivado otra ecuación, hay una nueva sustitución que se puede hacer en la original: n / 4 por n

En general, la ecuación básica es:

Suponiendo que n = 2 k permite:

Resolver relaciones de recurrencia mediante telescopio

La premisa para este tipo de solución es sustituir valores por n, sumar los resultados y eliminar términos semejantes. Por ejemplo:


El método maestro

El método Master es aplicable para resolver recurrencias del formulario.
$ begin T (n) = aT left ( frac right) + f (n) end$
donde $ a ge 0 $ y $ b ge 1 $ son constantes y $ f (n) $ es una función asintóticamente positiva. Dependiendo del valor de $ a, b $ y la función $ f (n) $, el método maestro tiene tres casos.

  1. Si $ f (n) = O (n ^ < log_b a- epsilon>) $ para una constante $ epsilon> 0 $, entonces $ T (n) = Theta (n ^ < log_b a>) $ .
  2. Si $ f (n) = Theta (n ^ < log_b a>) $, entonces $ T (n) = Theta (n ^ < log_b a> log n) $.
  3. Si $ f (n) = Omega (n ^ < log_b a + epsilon>) $ para algunos $ epsilon> 0 $ constantes, y si $ af (n / b) le cf (n) $ para algunos constante $ c 0 $ es una constante para $ i le i le k $
  4. $ b_i in (0, 1) $ es una constante para $ 1 le i le k $
  5. $ k ge 1 $ es una constante y,
  6. $ f (n) $ es una función no negativa

La solución de recurrencia dada en (2) es,
$ T (n) = Theta left (n ^ p left (1 + int_ <1> ^ frac<>

> du right) right) $
Previsto,
$ sum_^a_ib_i ^ p = 1 text $

Ejemplo 1: Considere una recurrencia,
$ T (n) = 2T (n / 4) + 3T (n / 6) + Theta (n log n) $

Para esta recurrencia, $ a_1 = 2, b_1 = 1/4, a_2 = 3, b_2 = 1/6, f (n) = n log n $. El valor de $ p $ se puede calcular como,
$ a_1b_1 ^ p + a_2b_2 ^ p = 2 times (1/4) ^ p + 3 times (1/6) ^ p = 1 $
$ p = 1 $ satisface la ecuación anterior. La solucion es
$ begin T (n) & = Theta left (n ^ p left (1 + int_ <1> ^ frac<>

> du right) right)
& = Theta left (n left (1 + int_ <1> ^ frac du right) right)
& = Theta left (n left (1 + frac < log ^ 2n> <2> right) right)
& = Theta (n log ^ 2n)
final$


Método de sustitución hacia atrás

En el método de sustitución hacia adelante, ponemos $ n = 0, 1, 2,… $ en la relación de recurrencia hasta que veamos un patrón. En sustitución hacia atrás, hacemos lo contrario, es decir, ponemos $ n = n, n - 1, n - 2,… $ o $ n = n, n / 2, n / 4,… $ hasta que veamos el patrón. Después de ver el patrón, hacemos conjeturas para el tiempo de ejecución y verificamos las conjeturas. Usemos este método en algunos ejemplos.

Considere un ejemplo de relación de recurrencia dada a continuación
$ T (n) = begin 1 & text n = 1 2T left ( frac <2> right) + n & text final$

Dado $ T (n) $, podemos calcular el valor de $ T (n / 2) $ a partir de la relación de recurrencia anterior como
$ T (n / 2) = 2T left ( frac <4> derecha) + frac<2>$
Ahora volvemos a sustituir el valor de $ T (n / 2) $ en $ T (n) $
$ T (n) = 2 ^ 2T left ( frac<2 ^ 2> derecha) + 2n $
Procedemos de manera similar
$ beginT (n) & = 2 ^ 3T left ( frac <2 ^ 3> derecha) + 3n
& = 2 ^ 4T left ( frac <2 ^ 4> derecha) + 4n
& = 2 ^ kT left ( frac <2 ^ k> derecha) + kn
final$
Ahora deberíamos usar la condición de límite (base), es decir, $ T (1) = 1 $. Para usar la condición de límite, la entidad dentro de $ T () $ debe ser 1, es decir,
$ frac <2 ^ k> = 1 $
Tomando $ log_2 $ en ambos lados,
$ n = log_2 n $
La ecuación (6) se convierte en
$ begin
T (n) & = 2 ^ < log_2 n> T left ( frac<2 ^ < log_2 n >> derecha) + log_2 n.n
& = nT (1) + n log_2 n
& = n log_2 n + n
final$
La exactitud del tiempo de ejecución anterior se puede demostrar mediante inducción. Ponga $ n = 2, 4, 8, 16,… $ y podrá verificar fácilmente que el tiempo de ejecución estimado es realmente correcto.

Rara vez usamos el método de sustitución hacia adelante y hacia atrás en los casos prácticos. Hay métodos mucho más sofisticados y rápidos. Pero estos métodos se pueden utilizar como último recurso cuando otros métodos no pueden resolver algunos tipos de recurrencias.


2.4: Resolver relaciones de recurrencia

En la publicación anterior, discutimos el análisis de bucles. Muchos algoritmos son de naturaleza recursiva. Cuando los analizamos, obtenemos una relación de recurrencia para la complejidad del tiempo. Obtenemos el tiempo de ejecución en una entrada de tamaño n en función de n y el tiempo de ejecución en entradas de tamaños más pequeños. Por ejemplo, en Merge Sort, para ordenar una matriz dada, la dividimos en dos mitades y repetimos el proceso de forma recursiva para las dos mitades. Finalmente fusionamos los resultados. La complejidad de tiempo de Merge Sort se puede escribir como T (n) = 2T (n / 2) + cn. Hay muchos otros algoritmos como Binary Search, Tower of Hanoi, etc.

Hay principalmente tres formas de resolver las recurrencias.

1) Método de sustitución: Adivinamos la solución y luego usamos la inducción matemática para demostrar que la suposición es correcta o incorrecta.

2) Método del árbol de recurrencia: En este método, dibujamos un árbol de recurrencia y calculamos el tiempo que tarda cada nivel de árbol. Finalmente, sumamos el trabajo realizado en todos los niveles. Para dibujar el árbol de recurrencia, partimos de la recurrencia dada y seguimos dibujando hasta encontrar un patrón entre niveles. El patrón suele ser una serie aritmética o geométrica.

3) Método maestro:
El método maestro es una forma directa de obtener la solución. El método maestro funciona solo para el siguiente tipo de recurrencias o para las recurrencias que se pueden transformar en el siguiente tipo.

Hay los siguientes tres casos:
1. Si f (n) = O (n c) donde c & lt LogBa entonces T (n) = Θ (n Log B a )

2. Si f (n) = Θ (n c) donde c = LogBa entonces T (n) = Θ (n c Log n)

3.Si f (n) = Ω (n c) donde c> LogBa entonces T (n) = Θ (f (n))

¿Como funciona esto?
El método maestro se deriva principalmente del método de árbol de recurrencia. Si dibujamos el árbol de recurrencia de T (n) = aT (n / b) + f (n), podemos ver que el trabajo realizado en la raíz es f (n) y el trabajo realizado en todas las hojas es Θ (nc) donde c es registroBuna. Y la altura del árbol de recurrencia es LogBnorte

En el método del árbol de recurrencia, calculamos el trabajo total realizado. Si el trabajo realizado en las hojas es polinomialmente mayor, entonces las hojas son la parte dominante y nuestro resultado se convierte en el trabajo realizado en las hojas (Caso 1). Si el trabajo realizado en las hojas y la raíz es asintóticamente igual, entonces nuestro resultado se convierte en altura multiplicada por el trabajo realizado en cualquier nivel (Caso 2). Si el trabajo realizado en la raíz es asintóticamente mayor, entonces nuestro resultado se convierte en trabajo realizado en la raíz (Caso 3).

Ejemplos de algunos algoritmos estándar cuya complejidad de tiempo se puede evaluar utilizando el método maestro
Combinar clasificación: T (n) = 2T (n / 2) + Θ (n). Cae en el caso 2 ya que c es 1 y LogBa] también es 1. Entonces la solución es Θ (n Logn)

Búsqueda binaria: T (n) = T (n / 2) + Θ (1). También cae en el caso 2 ya que c es 0 y LogBa también es 0. Entonces la solución es Θ (Logn)

Notas:
1) No es necesario que una recurrencia de la forma T (n) = aT (n / b) + f (n) se pueda resolver usando el Teorema maestro. Los tres casos dados tienen algunas brechas entre ellos. Por ejemplo, la recurrencia T (n) = 2T (n / 2) + n / Logn no se puede resolver con el método maestro.

2) El caso 2 se puede extender para f (n) = Θ (n c Log k n)
Si f (n) = Θ (n c Log k n) para alguna constante k> = 0 y c = LogBa, entonces T (n) = Θ (n c Log k + 1 n)

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema discutido anteriormente.

¡Atención lector! Don & rsquot deje de aprender ahora. Obtenga todos los conceptos importantes de DSA con el Curso autodidacta de DSA a un precio asequible para los estudiantes y prepárese para la industria. Para completar su preparación desde el aprendizaje de un idioma hasta DS Algo y muchos más, consulte Curso completo de preparación para entrevistas.


2.4: Resolver relaciones de recurrencia

El método del árbol de recurrencia es una forma de resolver las relaciones de recurrencia. En este método, una relación de recurrencia se convierte en árboles recursivos. Cada nodo representa el costo incurrido en varios niveles de recursividad. Para encontrar el costo total, se suman los costos de todos los niveles.

  1. Dibuja un árbol recursivo para una relación de recurrencia dada
  2. Calcule el costo en cada nivel y cuente el número total de niveles en el árbol de recursividad.
  3. Cuente el número total de nodos en el último nivel y calcule el costo del último nivel
  4. Sume el costo de todos los niveles en el árbol recursivo

Veamos cómo resolver estas relaciones de recurrencia con la ayuda de algunos ejemplos:

Pregunta 1: T (n) = 2T (n / 2) + c

  • Paso 2: Calcule el trabajo realizado o el costo en cada nivel y cuente el número total de niveles en el árbol de recursividad

Árbol recursivo con el costo de cada nivel

Cuente el número total de niveles & # 8211

Elija la ruta más larga desde el nodo raíz al nodo hoja

Tamaño del problema en el último nivel = n / 2 k

En el último nivel, el tamaño del problema se convierte en 1

No total de niveles en el árbol recursivo = k +1 = log2(n) + 1

  • Paso 3: Cuente el número total de nodos en el último nivel y calcule el costo del último nivel

T (n) = c + 2c + 4c + & # 8212- + (no. De niveles-1) veces + costo del último nivel

= c + 2c + 4c + & # 8212- + registro2(n) veces + Θ (n)

= c (1 + 2 + 4 + & # 8212- + registro2(n) veces) + Θ (n)

1 + 2 + 4 + & # 8212 & # 8211 + registro2(n) tiempos & # 8211> 2 0 + 2 1 + 2 2 + & # 8212 & # 8211 + log2 (n) tiempos & # 8211> Progresión geométrica (G.P.)

= c (norte) + Θ (norte)


Por lo tanto, T (n) = Θ (n)

Pregunta 2: T (n) = T (n / 10) + T (9n / 10) + n

  • Paso 2: Calcule el trabajo realizado o el costo en cada nivel y cuente el número total de niveles en el árbol de recursividad

Árbol de recursividad con el costo de cada nivel

Cuente el número total de niveles & # 8211

Elija la ruta más larga desde el nodo raíz al nodo hoja

(9/10) 0 n & # 8211> (9/10) 1 n & # 8211> (9/10) 2 n & # 8211> & # 8230 & # 8230 & # 8230 & # 8211> (9/10) k n

Tamaño del problema en el último nivel = (9/10) k n

En el último nivel, el tamaño del problema se convierte en 1

(9/10) k n = 1

(9/10) k = 1 / n

k = registro10/9(norte)

  • Paso 3: Cuente el número total de nodos en el último nivel y calcule el costo del último nivel

¡Atención lector! Don & rsquot deje de aprender ahora. Practique el examen GATE mucho antes del examen real con los cuestionarios generales y por materia disponibles en Curso de la serie de pruebas GATE.


3.2. Cuando T (n) = aT (n-1) + f (n)

Esto es un poco más complicado, porque a medida que los argumentos de la f caen, se multiplican por más y más a. Después de alguna sustitución hacia atrás, no es difícil reconocer el patrón

Ejemplo: T (n) = 2T (n-1) + n. Luego de la fórmula

Esto resulta ser una suma bastante dolorosa de resolver exactamente, pero podemos adivinar razonablemente que está en algún lugar entre 2 n y 2 n n, e intentar adivinar pero verificar para reducir aún más el rango.


Resolver relaciones no lineales

  • El teorema anterior es excelente si tiene una recurrencia lineal homogénea.
    • & hellip con raíces distintas.
    • Y el teorema relacionado en el texto puede manejar ecuaciones características con raíces repetidas.
    • Supongamos que ignoramos la parte no lineal y solo miramos la parte homogénea: [h_n = c_1h_ + c_2h_ + cdots + c_kh_,.]
    • Podemos resolver eso y obtener una fórmula para ().
    • Si tenemos suerte, podríamos encontrar una solución para () por algunos condiciones iniciales, pero quizás no las que nos interesan
    • Podemos usar el teorema anterior (o simplemente adivinar y demostrar) que las soluciones a (h_n = 3h_) tienen la forma (h_n = d cdot 3 ^).
    • Si estamos dispuestos a aceptar cualquier condición inicial, es posible que podamos obtener una solución particular ().
    • Podríamos suponer que podría haber una solución lineal en la forma (p_n = cn + d ) para algunas constantes (c, d ).
    • Estaríamos en lo cierto. Existe una solución de este tipo sif para todo (n & gt 1 ): [ begin p_n & amp = 3p_ + 2n cn + d & amp = 3 (c (n-1) + d) + 2n cn + d & amp = 3cn-3c + 3d + 2n 0 & amp = (2c + 2) n + (2d-3c) ,. final] Esto es cierto para todos (n ) iff (2c + 2 = 0 ) y (2d-3c = 0 ). Resolviendo estos, obtenemos (c = -1 ) y (d = -3 / 2 ).
    • Tenemos una solución para la recurrencia: (p_n = -n-3/2 ).
    • En realidad, esa no es una solución útil: estamos interesados ​​en (a_1 = 3 ) y eso no es lo que es (p_1 ). Tenemos las condiciones iniciales incorrectas.

    Teorema: Para una relación de recurrencia en la forma [a_n = c_1a_ + c_2a_ + cdots + c_ka_ + F (n) ,, ] si tenemos una solución a la parte lineal homogénea () (como se describe arriba), y una solución particular (), entonces todas las soluciones a la recurrencia están en la forma ().

    Prueba: Supongamos que tenemos alguna solución a la recurrencia original: (). Lo sabemos () también es una solución: [a_n = c_1a_ + c_2a_ + cdots + c_ka_ + F (n) p_n = c_1p_ + c_2p_ + cdots + c_kp_ + F (n) ]

    Restando estos, obtenemos [a_n-p_n = c_1 (a_-pag_) + c_2 (a_-pag_) + cdots + c_k (a_-pag_)] Por lo tanto, () es una solución a la parte homogénea, ().

    Entonces, cualquier solución () se puede escribir en la forma () para alguna solución a la recurrencia homogénea. ∎

    • El teorema anterior nos dice que todas las soluciones a la recurrencia se parecen a (a_n = d cdot 3 ^-n-3/2 ).
    • Solo tenemos que completar (d ): [ begin a_1 & amp = 3 d cdot 3 ^ <1> -1-3 / 2 & amp = 3 d & amp = 11/6 ,. final]
    • Finalmente tenemos (a_n = 11/6 cdot 3 ^-n-3/2 ).
    • La parte homogénea de esto es (h_n = 2h_). Podríamos adivinar, pero usemos el teorema.
    • La ecuación característica para esta recurrencia es (r-2 = 0 ) que tiene la solución (r = 2 ). Por lo tanto, las soluciones tienen la forma (h_n = d cdot2 ^ n ).
    • Para una solución particular, adivine que (p_n = c cdot 3 ^ n ) para algunos (c ). Podemos confirmar la suposición encontrando una constante (c ). Para hacer esto, sustituimos en la recurrencia: [ begin p_n & amp = 2p_+ 3 ^ n c cdot 3 ^ n & amp = 2 (c cdot 3 ^) + 3 ^ n c (3 ^ n-2 cdot 3 ^) & amp = 3 ^ n c (3-2) & amp = 3 ^ n / 3 ^ c & amp = 3 ,. final]
    • Tenemos una solución particular (para condiciones iniciales no particulares) de (p_n = 3 ^).
    • Ahora podemos satisfacer (a_n ) para nuestra condición inicial ya que todas las soluciones a () tienen el formato [ begin a_n & amp = d2 ^ n + 3 ^ 5 = a_1 & amp = d2 ^ 1 + 3 ^ 2 5 & amp = 2d + 3 d & amp = 2 ,. final]
    • Entonces, (a_n = 2 ^+ 3^).
    • La parte homogénea tiene la ecuación característica (r ^ 2-5r-6 = 0 ), entonces raíces (r_1 = 6, r_2 = -1 ).
    • Entonces, las soluciones tienen la forma (h_n = d_1 6 ^ n + d_2 (-1) ^ n ).
    • Para una solución particular, deberíamos encontrar algo en la forma (p_n = c cdot 7 ^ n ): [ begin p_n = c cdot 7 ^ n & amp = 5c cdot 7 ^+ 6c cdot 7 ^+ 7 ^ n c cdot 7 ^ 2 & amp = 5c cdot 7 ^ 1 + 6c cdot 7 ^ 0 + 7 ^ 2 0 & amp = 49/8 ,. final]
    • Entonces tenemos (p_n = frac <49> <8> cdot 7 ^ n ).
    • Del teorema, [a_n = d_1 6 ^ n + d_2 (-1) ^ n + tfrac <49> <8> cdot 7 ^ n ,. ]
    • Sustituyendo (a_0 ) y (a_1 ), obtenemos [1 = d_1 + d_2 + tfrac <49> <8> text 6 = 6d_1-d_2 + tfrac <343> <8> , , d_1 = -6 text d_2 = tfrac <7> <8> ,. ]
    • Así tenemos una solución: [a_n = -6 cdot 6 ^ n- tfrac <7> <8> cdot (-1) ^ n + tfrac <49> <8> cdot 7 ^ n = tfrac <1> <8> left (-8 cdot 6 ^ - 7 (-1) ^ n + 7 ^derecho) ,.]
    • Definitivamente no habría llegado a eso sin el teorema para ayudar.

    4. El teorema maestro

    El Teorema principal proporciona soluciones asintóticas instantáneas para muchas recurrencias de la forma T (n) = aT (n / b) + f (n), que se aplican a todos los valores de n (no solo a las potencias de b). Se basa en aplicar el análisis de la sección anterior a varias familias amplias de funciones f, y luego extender los resultados usando un argumento de monotonicidad a valores de n que no son potencias de b. Aquí esbozamos la prueba; consulte el Apéndice B de LevitinBook para obtener un argumento más detallado.

    Si f (n) = 0, entonces la recurrencia es simplemente T (n) = aT (n / b). Esto tiene la solución T (n) = n log [b] a T (1) = Θ (n log [b] a). (Ejemplo: T (n) = 4T (n / 2) tiene la solución Θ (n lg 4) = Θ (n²).) Clasificamos diferentes casos del Teorema maestro en función de cómo f (n) se compara con esta solución predeterminada.

    Suponemos que T (1) = Θ (1) en todo momento.

    Suponga que f (x) = x c. Entonces a i f (n / b i) = a i n c / b ic = n c (a / b c) i. La suma es entonces una serie geométrica con razón (a / b c), y su comportamiento depende críticamente de si (a / b c) es menor que 1, igual a 1 o mayor que 1.

    Si (a / b c) es menor que 1, entonces Sigmai = 0 hasta el infinito norte c (a / segundo c) yo = norte c / (1- (a / segundo c)) = O (norte c). Este caso surge cuando log (a / b c) = log a - c log b es menor que cero, lo cual ocurre precisamente cuando c & gt log a / log b = logB una. Entonces, si f (n) = nc, el término f (n) en la suma domina tanto el resto de la suma como el n log [b] a término, y obtenemos T (n) = Θ (f (n)) . Si f (n) es Omega (nc), pero satisface el requisito técnico adicional de que af (n / b) & lt = (1-delta) f (n) para todo n y algún delta fijo & gt 0, entonces el argumento de la serie geométrica todavía funciona con el factor (1-delta), y todavía obtenemos T (n) = Θ (f (n)). Esto cubre el caso donde f (n) = Omega (n log [b] a + épsilon).

    Si (a / b c) es igual a 1, entonces todos los términos de la suma son iguales y el total es f (n) logB norte. En este caso c = logB a, entonces f (n) = n log [b] ay f (n) logB n domina (apenas) el término T (1). Una versión extendida de este análisis muestra que la solución es T (n) = Θ (f (n) log n) cuando f (n) = Θ (n log [b] a).

    Finalmente, si (a / b c) es mayor que 1, tenemos una serie geométrica cuya suma es proporcional a su último término, que se puede demostrar que es asintóticamente menor que el término T (1). Este caso da T (n) = Θ (n log [b] a) para cualquier f (n) = O (n log [b] a - épsilon).

    Estos tres casos no cubren todas las posibilidades (considere T (n) = 2T (n / 2) + n log n), pero manejarán la mayoría de las recurrencias de esta forma que probablemente encontrará.


    Esto parece bastante cercano a la respuesta correcta.

    Cuando $ k = lceil ln (n) / ln (7) rceil $, $ n le 7 ^ k $, entonces $ A ( lceil n / 7 ^ k rceil) = 1 $.

    Poniendo esto en tu ecuación, $ A (n) = 4 ^ k + 4 ^ k lfloor n / 7 ^ k rfloor ^ 2. +4 lpiso n / 7 rpiso ^ 2 + n ^ 2 $.

    Para obtener un límite superior, ya que $ lfloor x rfloor le x le lceil x rceil & lt x + 1 $, $ 4 ^ k & lt 4 ^ <1+ ln (n) / ln (7)> = 4n ^ < ln (4) / ln (7)> ​​& lt 4n $ entonces $ A (n) & lt 4n + n ^ 2 (4 ^ k / 7 ^ k +. + 4/7 + 1) & lt 4n + n ^ 2 / (1-4 / 7) & lt 4n + 7 n ^ 2/3 $.

    En este caso, la serie que multiplica $ n ^ 2 $ converge.

    Intente resolver esto con el 4 y el 7 intercambiados, de modo que $ A () = 7A ( lpiso rfloor) + n ^ 2 $.