Algoritmos | Recurrencias | Serie 1

julio 5, 2022 Rudeus Greyrat

Pregunta 1: ¿Cuál de los siguientes es el valor de T ³ (n) donde T ³ (n) se define como T ³ (n) = 5*T ³ (n-1) – 4*T ³ (n-2)
1. C ₁ * 5 ^norte + C ₂ * 4 ^norte
2. do ₁ + do ₂ *4 ^norte
3. C ₁ * 2 ^norte + C ₂ * 4 ^norte
4. C ₁ * 5 ^norte + C ₂ * (-4) ^norte
Respuesta: 2

Explicación: La función de recursión (ecuación) parece tener una forma extraña. Cambiemos la variable T ² (n) para obtener una ecuación de forma familiar; entonces, hacemos A(n) = T ³ (n); entonces tenemos:

$A(n) = 5*A(n - 1) - 4*A(n - 2)$

La ecuación característica de nuestra nueva ecuación diferencial sería:

$r^{2} - 5*r + 4 = 0 \Rightarrow (r-4)(r-1) = 0$

Entonces, la solución homogénea de esta ecuación será:

$A(n) = C_{1} * 1^{n} + C_{2} * 4^{n} = C_{1} + C_{2} * 4^{n}$

Como hemos definido A(n) = T ³ (n), la respuesta final es:

$T^{3}(n) = C_{1} + C_{2} * 4^{n} = C_{1} + C_{2} * 4^{n}$
Pregunta 2: ¡Determine el valor de la condición inicial F(1) de manera que podamos tener F(n) = (n+2)! como la solución a la siguiente función recursiva dada:
```
 F(n) = (n+1) * F(n-1) + (n+1)! 
```
1. 3
2. 4
3. 6
4. 2
Respuesta: 3

Explicación: Mediante el uso de la técnica de iteración para resolver la función recursiva dada, tendremos:

$F(n) = (n+1) * F(n - 1) + (n+1)! = (n+1) * (n*F(n-2) + n!) + (n+1)! =(n+1)*(n)*F(n-2) + 2* (n+1)!$

Si continuamos con estas derivaciones, podemos adivinar fácilmente que la respuesta debería ser de la siguiente forma:

$F(n) = (n+1)(n)(n - 1)* ... *(n - k + 2)F(n - k) + k * (n+1)!$

El último paso (punto de parada) en el método de iteración es cuando alcanzamos la condición inicial F(1); por lo tanto, hacemos k = n-1, y la forma no recursiva sería:

$F (n) = (n + 1)*(n)*(n - 1)*...*(3) * F(1) + (n - 1) * (n+1)!$

$= (n + 1)*(n)*(n - 1)*...*(3) * (2 * \frac{1}{2}) * F(1) + (n - 1) * ( n+1)!$

$= (n+1)! * ( \frac{F(1)}{2}) + (n - 1) * (n+1)! = (n+1)! * (\frac{F(1)}{2} + (n - 1))$

De acuerdo con la función dada F(n) en cuestión, y lo que hemos derivado hasta ahora:

$F(n) = (n+2)! = (n+1)! * (n+2) = (n+1)! * (\frac{F(1)}{2} + (n - 1))$

Finalmente, como veremos, el valor de F(1) es:

$F(1) = 2*(n + 2) - 2*(n - 1) = 6$
Pregunta 3: ¿Cuál es la complejidad temporal de T(n) = 4* T(n/2) + n * log(n!).
1. θ(n * registro n)
2. θ(n ² )
3. θ(n ² * log n)
4. θ(n ² * log ² n)
Respuesta: 4

Explicación: Sabemos que log(n!) ∈ θ( norte * iniciar sesión norte ) .

Ahora, el problema equivalente es analizar el orden de la nueva función recursiva:

$T(n) = 4 * T(\frac{n}{2}) + n^{2} * log(n)$

Podemos resolver esto por el teorema maestro . Para aplicar aquí el teorema maestro, tenemos f(n) = n ² * log(n) , y los parámetros a (el número de subproblemas), b (el factor de reducción) y C igual a 4, 2 , y 2, respectivamente; entonces, θ( n ^{log _b a} ), es de θ( n ² ) que se encuentra en la misma clase de complejidad de θ( n ^{C = 2} ); por lo tanto, la función recursiva dada pertenece al caso 2 del teorema maestro.

De acuerdo con el teorema del maestro, T(n) sería del siguiente orden:

$T(n) \in \theta(n^{2} * log^{2}n )$
Pregunta 4: ¿Cuál da la mejor estimación de la complejidad de T(n)?
```
T (n) =  * T(n/2)+ n² √. 
```
1. θ( n ² * √ * log n )
2. O( n ² * √ * log n )
3. θ( $n^{log_{2}6}$ )
4. θ( $n^{log_{3}6}$ )
5. O( n ² * √ ).
Respuesta: 3

Explicación: Sabemos que $a^{log_{b}C} = C^{log_{b}a}$ , y $n^{2}*\sqrt(n+1) \in \theta (n^{2 + \frac{1}{2}}) \in \theta (n^{\frac{5}{2}})$ ; entonces, podemos simplificar la función de recursión de la siguiente manera:

$T(n) = 3^{log_{3}6} * T(\frac{n}{2}) + n * \sqrt(n+1) = 6* T(\frac{n}{2}) + \theta ( n^{\frac{5}{2}} )$

Pertenece al caso 3 del teorema maestro ; entonces, la complejidad asintótica de T(n) es:

$T(n) \in \theta ( n^{log_{2}6} )$
Pregunta 5: ¿Qué límite asintótico no es correcto para T (n) = T (n/4) + T (3n/4) + n?
1. O( n ^{log _4/3 2} )
2. Ω( n )
3. O( n * log(n) )
4. Ninguna de las anteriores
Respuesta: 4

Explicación: Por el teorema maestro , podemos especificar los mismos límites que se indican en las dos primeras opciones (A) y (B):
1. $T(n) = T(\frac{n}{4}) + T(\frac{3n}{4}) + n \leq 2*T(\frac{3n}{4})+n \Rightarrow T(n) \in O (n^{ log_{4/3}2})$
2. $T(n) = T(\frac{n}{4}) + T(\frac{3n}{4}) + n \geq 2*T(\frac{n}{4})+n \Rightarrow T(n) \in \Omega (n)$
Podemos averiguar la corrección de la tercera opción mediante el método del árbol de recurrencia . Dibujamos un árbol y podemos adivinar fácilmente un límite apropiado para T(n) :

La longitud de las ramas del árbol de recurrencia no puede ser inferior a h _r , ni tampoco puede ser superior a h _L ; por lo que se pueden inferir las siguientes estimaciones:
1. $T(n) \leq n * h_{r} = n * log_{\frac{4}{3}}n \Rightarrow T(n) \in O( n*log(n) )$
2. $T(n) \geq n * h_{L} = n * log_{4}n \Rightarrow T(n) \in \Omega ( n*log(n) )$
De acuerdo con los dos límites mencionados anteriormente, también tenemos T(n) ∈ θ( n*log(n) ) .

Sabemos que si T(n) ∈ O(n * log(n)) , debe ser también de O(n ^{log _4/3 n} ) ; por lo tanto, si evaluamos primero la tercera opción, en realidad también habríamos inferido la corrección de la opción (A). Sin embargo, los árboles de recurrencia solo dan una idea de cómo adivinar un límite apropiado. Como alguien puede dar una suposición equivocada, este método también necesita verificación o prueba de que no violará la definición de las notaciones en uso. Esta verificación (prueba) puede obtenerse inductivamente mediante sustituciones iterativas en T(n), considerando las definiciones de la notación.

Publicación traducida automáticamente

Artículo escrito por j*g*1991 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta Cancelar la respuesta