¿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 sólo de esa manera?

Answer 1

Piénsalo de esta manera:
En cada una "repetición" de la recursividad haces O (n) el trabajo.
Cada iteración tiene n-1 trabajo por hacer, hasta que caso n = base. (Estoy asumiendo caso base es O (n) de trabajo)
Por lo tanto, suponiendo que el caso base es un independiente constante de n, hay O (n) iteraciones de la recursión.
Si tiene n iteraciones de O (n) cada trabajo, O (n) * O (n) = O (n ^ 2).
Su análisis es correcto. Si desea más información sobre esta forma de recurrencias de resolución, mira en la recursividad árboles. Son muy intuitiva en comparación con los otros métodos.

Answer 2

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

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

Para solucionar esto, se puede adivinar por primera vez una solución y luego demostrar que funciona por inducción.

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

En primer lugar el caso base. Cuando n = 1 esto da c según se requiera.

En 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í funciona la solución.

Para obtener la conjetura, en primer lugar, el aviso de que su relación de recurrencia genera la números triangulares 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 Big-O notación las constantes puede ser ignorada por lo O (n ^ 2) es el resultado esperado.

Answer 3

La solución es bastante fácil para éste. 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 

Se tiene aquí progresión aritmética y la suma es 1/2*n*(n-1). Técnicamente se echa en falta la condición de frontera aquí, pero con cualquier condición de contorno constante que se ve que la recursividad es O(n^2).

Answer 4

mira alrededor derecha, pero dependerá del caso base T (1). Suponiendo que va a hacer n pasos para obtener T (n) a T (0) y cada vez que el término n es cualquier lugar entre 0 y n para un promedio de n / 2, de modo n * n / 2 = (n ^ 2) / 2 = O (n ^ 2).