Use la siguiente solución bajo su propio riesgo.
Podemos utilizar el método de sustitución para resolver la recurrencia. El método de sustitución para resolver las recurrencias consta de dos pasos:
1. Adivina la forma de la solución.
2. Use la inducción matemática para encontrar las constantes y mostrar que la solución
trabajos.
Sustituimos la solución adivinada por la función cuando aplicamos el inductivo
hipótesis a valores más pequeños; de ahí el nombre “método de sustitución” (de CLRS).
supongo que T (n) <= a * (n) -b, donde a y b son constantes.
T (n ^ 1/2) <= a * (n ^ 1/2) -b
pon este valor en nuestra recursividad.
T (n) <= n ^ 1/2 * (a * n ^ 1/2-b) + n ^ 1/2
T (n) = a * n + (1-b) * n ^ 1/2,
T (n) = a * n + (1-b) * n ^ 1/2 + bb
T (n) = a * n-b + (1-b) * n ^ 1/2 + b
Para b suficientemente grande y algo de n0, la parte de la ecuación anterior que es (1-b) * n ^ 1/2 + b será negativa.
T (n) <= a * (n ^ 1/2) -b
Por lo tanto, T (n) ∈ O (n).
O puede sustituir el valor de T (n ^ 1/2) = n ^ 1 / 4T (n ^ 1/4) + n ^ 1/4 y luego T (n ^ 1/4) y T (n ^ 1 / 8) etc.
Llegar
T (n) = n ^ 1/2 (n ^ 1/4 T (n ^ 1/4) + n ^ 1/4) + n ^ 1/2
T (n) = n ^ 1/2 (n ^ 1/4 (n ^ 1/8 T (n ^ 1/8) + n ^ 1/8) + n ^ 1/4) + n ^ 1/2
.
.
.
T (n) ∈ n ^ (1/2 + 1/4 + 1/8 +… ..)
T (n) ∈ n ^ 1
T (n) ∈ O (n).
Cómo resolver la relación de recurrencia [matemáticas] T (n) = n ^ {1/2} T (n ^ {1/2}) + n ^ {1/2} [/ matemáticas] usando el método de sustitución
La respuesta es [matemáticas] O (n) [/ matemáticas].
Asumo el caso base como T (2) = 2
[matemáticas] T (n) = n ^ {\ frac {1} {2}} T (n ^ {\ frac {1} {2}}) + n ^ {\ frac {1} {2}} [/ matemáticas]
[matemáticas] \ implica T (n) = n ^ {\ frac {1} {2}} (n ^ {\ frac {1} {4}} T (n ^ {\ frac {1} {4}}) + n ^ {\ frac {1} {4}}) + n ^ {\ frac {1} {2}} [/ math]
Después de la primera sustitución
[matemáticas] \ implica T (n) = n ^ {\ frac {1} {2} + \ frac {1} {4}} T (n ^ {\ frac {1} {4}}) + n ^ { \ frac {1} {2} + \ frac {1} {4}} + n ^ {\ frac {1} {2}} [/ matemáticas]
Después de la 2da sustitución
[matemáticas] \ implica T (n) = n ^ {\ frac {1} {2} + \ frac {1} {4} + \ frac {1} {8}} T (n ^ {\ frac {1} {8}}) + n ^ {\ frac {1} {2} + \ frac {1} {4} + \ frac {1} {8}} + n ^ {\ frac {1} {2} + \ frac {1} {4}} + n ^ {\ frac {1} {2}} [/ math]
Después de la sustitución [math] (k-1) ^ {th} [/ math]
[matemáticas] \ implica T (n) = n ^ {\ frac {1} {2} + \ frac {1} {2 ^ 2} + \ frac {1} {2 ^ 3} + \ cdots + \ frac { 1} {2 ^ k}} T (n ^ {\ frac {1} {2 ^ k}}) + n ^ {\ frac {1} {2} + \ frac {1} {2 ^ 2} + \ frac {1} {2 ^ 3} + \ cdots + \ frac {1} {2 ^ k}} + \ cdots + n ^ {\ frac {1} {2} + \ frac {1} {2 ^ 2} + \ frac {1} {2 ^ 3}} + n ^ {\ frac {1} {2} + \ frac {1} {2 ^ 2}} + n ^ {\ frac {1} {2}} [ /matemáticas]
Lo sabemos
[matemáticas] \ frac {1} {2} + \ frac {1} {2 ^ 2} + \ frac {1} {2 ^ 3} + \ cdots + \ frac {1} {2 ^ k} = 1- \ frac {1} {2 ^ k} [/ matemáticas]
[matemáticas] \ implica T (n) = n ^ {1- \ frac {1} {2 ^ k}} T (n ^ {\ frac {1} {2 ^ k}}) + n ^ {1- \ frac {1} {2 ^ k}} + \ cdots + n ^ {1- \ frac {1} {2 ^ 3}} + n ^ {1- \ frac {1} {2 ^ 2}} + n ^ {\ frac {1} {2}} [/ matemáticas]
Deje que [matemáticas] n ^ {\ frac {1} {2 ^ k}} = 2 [/ matemáticas]
[matemáticas] \ implica \ frac {1} {2 ^ k} = \ log_n (2) [/ matemáticas]
[matemáticas] \ implica T (n) = n ^ {1- \ log_n 2} T (2) + n ^ {1- \ log_n 2} + \ cdots + n ^ {1- \ frac {1} {2 ^ 3}} + n ^ {1- \ frac {1} {2 ^ 2}} + n ^ {\ frac {1} {2}} [/ matemáticas]
[matemáticas] \ implica T (n) = 2 * \ frac {n} {2} + \ cdots + n ^ {1- \ frac {1} {2 ^ 3}} + n ^ {1- \ frac {1 } {2 ^ 2}} + n ^ {\ frac {1} {2}} [/ math]
Después de descuidar los términos inferiores …
[matemáticas] T (n) = O (n / 2) = O (n) [/ matemáticas]
Gracias por A2A 🙂
parece que tienes tu respuesta
Lo habría solucionado siguiendo los métodos de sustitución y maestro.
