Come risolvere: T (n) = T (n - 1) + n

Question

Ho il seguente elaborato:

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

Ora, quando lavoro questo fuori trovo che il limite è molto sciolto. Ho fatto qualcosa di sbagliato o è solo in questo modo?

Answer 1

Pensare in questo modo:
In ogni "ripetizione" della ricorsione che fai O (n) di lavoro.
Ogni iterazione ha n-1 lavoro da fare, finché caso n = base. (Sto assumendo caso base è O (n) di lavoro)
Pertanto, assumendo il caso base è una costante indipendente di n, ci sono O (n) iterazioni del ricorsione.
Se si dispone di n iterazioni di O (n) lavoro ogni, O (n) * O (n) = O (n ^ 2).
La tua analisi è corretta. Se desideri ulteriori informazioni su questo modo di ricorsioni solving, guardare in ricorsione Alberi. Sono molto intuitivo rispetto agli altri metodi.

Answer 2

È necessario anche un caso base per la vostra relazione di ricorrenza.

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

Per risolvere questo problema, è possibile prima indovinare una soluzione e poi dimostrare che funziona con l'induzione.

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

In primo luogo il caso base. Quando n = 1 questo dà c come richiesto.

Per gli altri 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

Così le opere di soluzione.

Per ottenere l'ipotesi, in primo luogo, si noti che il vostro rapporto ricorrenza genera il numeri triangolari quando c = 1:

T(1) = 1:

*

T(2) = 3:

*
**

T(3) = 6:

*
**
***

T(4) = 10:

*
**
***
****

etc..

Intuitivamente un triangolo è circa la metà di un quadrato, o Big notazione O-le costanti può essere ignorato quindi O (n ^ 2) è il risultato previsto.

Answer 3

La soluzione è abbastanza facile per questo. È necessario srotolare la ricorsione:

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 

Hai progressione aritmetica qui e la somma è 1/2*n*(n-1). Tecnicamente si sta perdendo la condizione al contorno qui, ma con qualsiasi condizione al contorno costante si vede che la ricorsione è O(n^2).

Answer 4

appare sul diritto, ma dipenderà dal caso base T (1). Supponendo che si farà n passi per ottenere T (n) a T (0) e ogni volta che il termine n è ovunque tra 0 e n per una media di n / 2 in modo da n * n / 2 = (n ^ 2) / 2 = O (n ^ 2).