¿Cómo resolver: T (n) = T (n - 1) + n

Question

Tengo el siguiente funcionado:

T(n) = T(n - 1) + n = O(n^2) 

Ahora cuando trabajo esto me parece que la cota es muy floja. ¿He hecho algo mal o es solo así?

Answer 1

Piénselo de esta manera:
En cada "iteración" de la recursión, usted hace O (n) trabajo.
Cada iteración tiene n-1 trabajo por hacer, hasta n = caso base. (Supongo que el caso base es O (n) trabajo)
Por lo tanto, suponiendo que el caso base es una constante independiente de n, hay O (n) iteraciones de la recursión.
Si tiene n iteraciones de O (n) cada una, O (n) * O (n) = O (n^2).
Su análisis es correcto. Si desea obtener más información sobre esta forma de resolver recursiones, busque Árboles de recursión. Son muy intuitivos en comparación con los otros métodos.

Answer 2

También necesita un caso base para su relación de recurrencia.

T(1) = c 
T(n) = T(n-1) + n 

Para resolver esto, primero puede adivinar una solución y luego probar que funciona mediante inducción.

T(n) = (n + 1) * n/2 + c - 1 

Primero la caja base. Cuando n = 1 esto da c como se requiere.

Por otra n:

T(n) 
= (n + 1) * n/2 + c - 1 
= ((n - 1) + 2) * n/2 + c - 1 
= ((n - 1) * n/2) + (2 * n/2) + c - 1 
= (n * (n - 1)/2) + c - 1) + (2 * n/2) 
= T(n - 1) + n 

Así que la solución funciona.

Para obtener el conjetura, en primer lugar, observe que su relación de recurrencia genera la triangular numbers cuando c = 1:

T(1) = 1: 

* 

T(2) = 3: 

* 
** 

T(3) = 6: 

* 
** 
*** 

T(4) = 10: 

* 
** 
*** 
**** 

etc.. 

Intuitivamente un triángulo es aproximadamente la mitad de un cuadrado, y en notación Big-O el las constantes se pueden ignorar, por lo que O (n^2) es el resultado esperado.

Answer 3

Parece correcto, pero dependerá de la caja base T (1). Suponiendo que hará n pasos para obtener T (n) a T (0) y cada vez que el término n esté entre 0 y n para un promedio de n/2, entonces n * n/2 = (n^2)/2 = O (n^2).

Answer 4

La solución es bastante fácil para esta. Usted tiene que desenrollar la recursividad:

T(n) = T(n-1) + n = T(n-2) + (n - 1) + n = 
= T(n-3) + (n-2) + (n-1) + n = ... = 
= T(0) + 1 + 2 + ... + (n-1) + n 

usted tiene aquí progresión aritmética y la suma se 1/2*n*(n-1). Técnicamente te estás perdiendo la condición de límite aquí, pero con cualquier condición de límite constante ves que la recursión es O(n^2).