Cómo resolver la recurrencia T (n) = T (n – 1) + n usando el teorema del maestro

Gracias por el A2A.

El teorema maestro no funciona para esta relación de recurrencia.
(Seguiré la notación del teorema del Maestro).

Si queremos expresar esto en la forma [matemáticas] T (n) = a T (\ frac {n} {b}) + f (n) [/ matemáticas], obtenemos [matemáticas] a = 1, f ( n) = n, b = \ frac {n} {n-1} [/ math].
Está claro que [math] b [/ math] no es una constante. Sin embargo, tenemos algunos límites en [matemáticas] b [/ matemáticas]: [matemáticas] 1

Podríamos calcular el límite usando los límites superior e inferior en [matemáticas] b [/ matemáticas], pero desafortunadamente el límite importante 1 (al que convergerá) no es un valor aceptable para el teorema maestro.
Tendríamos que comparar c = 1 con log_1 (1), que no está definido.
El teorema maestro es útil para algoritmos de estilo de divide y vencerás donde siempre disminuimos [matemática] n [/ matemática] en alguna fracción para la próxima llamada.

La recurrencia dada es de la forma:
T (n) = aT (nb) + f (n), n> 1 para algunas constantes c, a> 0, b> 0, k> = 0 y la función f (n) y podría resolverse usando Restar y conquistar recurrencia método.
Si f (n) tiene la forma n ^ k, entonces,
T (n) = {O (n ^ k), si a <1
O (n ^ (k + 1)), si a = 1
O (n ^ ka ^ (n / b)), si a> 1}

Ahora a tu pregunta,
T (n) = T (n-1) + n
Comparándolo con la relación de recurrencia general mencionada anteriormente obtenemos
a = 1, b = 1, k = 1 (ya que f (n) = n ^ 1)
Como a = 1, entonces desde arriba T (n) = O (n ^ (k + 1)), sustituya el valor de k y obtendremos nuestra respuesta T (n) = O (n ^ 2) .
Fácil con este enfoque. 😀

Aquí está la clasificación de las recurrencias que se pueden resolver usando el Teorema del Maestro:

1. Resuelve las recurrencias de la forma T (n) = a * T (n / b) + f (n).
2. Aquí ” a” debe ser mayor o igual que 1. Lo que significa que el problema se reduce al menos a un subproblema más pequeño una vez. Se necesita al menos una recursión.
3. Aquí ” b” debe ser mayor que 1. Lo que significa que en cada recursión, el tamaño del problema se reduce a un tamaño menor. Si b no es mayor que 1, eso significa que nuestros subproblemas no son de menor tamaño.
4. f (n) debe ser positivo para valores relativamente grandes de n.

Dado que la recurrencia T (n) = T (n – 1) + n no sigue el patrón T (n) = a * T (n / b) + f (n) Por lo tanto, no puede ser resuelto por Master Theorem.

Fuera de lo puramente mecánico, el método de generar funciones muestra frutos con una cantidad modesta de esfuerzo. Asumimos que:

[matemáticas] t_0 = 0, n \ geqslant 1 \ etiqueta * {} [/ matemáticas]

Empezando con:

[matemáticas] t_n = t_ {n-1} + n \ tag {1} [/ matemáticas]

buscamos una función:

[matemáticas] \ displaystyle g (x) = \ sum_ {n \ geqslant 1} t_n x ^ n \ tag {2} [/ matemáticas]

tal que [math] t_n [/ math] se expresa en forma cerrada con respecto a [math] n [/ math].

Multiplique ambos lados de ( 1 ) por [matemáticas] x ^ n [/ matemáticas] y sume ambos lados sobre los valores legales de [matemáticas] n [/ matemáticas]:

[matemáticas] \ displaystyle \ sum_ {n \ geqslant 1} t_n x ^ n = \ sum_ {n \ geqslant 1} t_ {n-1} x ^ n + \ sum_ {n \ geqslant 1} nx ^ n \ tag { 3} [/ matemáticas]

En el lado izquierdo de ( 3 ) tenemos exactamente [matemáticas] g (x) [/ matemáticas]. La primera suma en el lado derecho de ( 3 ) es casi [matemática] g (x) [/ matemática]: factoriza su primer poder de [matemática] x [/ matemática] para obtener [matemática] g (x) [ /mates]:

[matemáticas] \ displaystyle \ sum_ {n \ geqslant 1} t_ {n-1} x ^ n = x \ sum_ {n \ geqslant 1} t_ {n-1} x ^ {n-1} = x \ cdot g (x) \ tag {4} [/ math]

Por lo tanto:

[matemáticas] \ displaystyle g (x) = x \ cdot g (x) + \ sum_ {n \ geqslant 1} nx ^ n \ tag {5} [/ matemáticas]

Dada la última suma en el lado derecho de ( 5 ), encuentre su expresión de forma cerrada en funciones elementales diferenciando la serie de potencia geométrica una vez con respecto a [math] x [/ math]:

[matemáticas] \ dfrac {1} {1-x} = \ sum x ^ n \ tag {6} [/ matemáticas]

[matemáticas] \ Big (\ dfrac {1} {1-x} \ Big) ‘_ x = \ dfrac {1} {(1-x) ^ 2} = \ dfrac {1} {x} \ sum nx ^ n \ tag {7} [/ math]

de donde se sigue que:

[matemáticas] \ sum nx ^ n = \ dfrac {x} {(1-x) ^ 2} \ tag {8} [/ matemáticas]

Ponga ( 8 ) en ( 5 ):

[matemáticas] g (x) = x \ cdot g (x) + \ dfrac {x} {(1-x) ^ 2} \ tag {9} [/ matemáticas]

y resuelve ( 9 ) para [matemáticas] g (x) [/ matemáticas]:

[matemáticas] g (x) = \ dfrac {x} {(1-x) ^ 3} \ tag {10} [/ matemáticas]

Aquí tenemos que realizar el inverso de la operación ( 8 ): dada una función, encontrar su serie de potencias: diferenciar ( 6 ) dos veces con respecto a [matemáticas] x [/ matemáticas] y multiplicar ambos lados del resultado por la primera potencia de [matemáticas] x [/ matemáticas] para obtener:

[matemáticas] \ displaystyle g (x) = \ dfrac {x} {(1-x) ^ 3} = \ sum_ {n \ geqslant 1} \ dfrac {1} {2} n (n + 1) x ^ n \ tag {11} [/ matemáticas]

En consecuencia, para [math] t_n [/ math], como una función de forma cerrada en términos de [math] n [/ math], tenemos:

[matemáticas] t (n) = \ dfrac {1} {2} n (n + 1) \ tag {12} [/ matemáticas]