Comment résoudre: T (n) = T (n - 1) + n

Question

Je donne les résultats suivants élaboré:

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

Maintenant, quand je travaille sur ce que je trouve que la limite est très lâche. Ai-je fait quelque chose de mal ou est-ce juste de cette façon?

Answer 1

Pensez-y de cette façon:
Dans chaque « itération » de la récursion que vous faites le travail O (n).
Chaque itération a n-1 à faire, jusqu'à ce que n = cas de base. (Je suppose cas de base est un travail O (n))
Par conséquent, en supposant que le cas de base est une constante indépendante de n, il y a O (n) itérations de la récursion.
Si vous avez n itérations de O (n) travail chacun O (n) * O (n) = O (n ^ 2).
Votre analyse est correcte. Si vous souhaitez plus d'informations sur cette façon de résoudre des récurrences, regard sur les arbres récursivité. Ils sont très intuitifs par rapport aux autres méthodes.

Answer 2

Il faut aussi un cas de base pour votre relation de récurrence.

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

Pour résoudre ce problème, vous pouvez deviner d'abord une solution, puis prouver qu'il fonctionne par induction.

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

Tout d'abord le cas de base. Lorsque n = 1 cela donne c au besoin.

Pour les autres 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

Ainsi, les travaux de solution.

Pour obtenir la conjecture en premier lieu, notez que votre relation de récurrence génère le nombre triangulaires lorsque c = 1:

T(1) = 1:

*

T(2) = 3:

*
**

T(3) = 6:

*
**
***

T(4) = 10:

*
**
***
****

etc..

Intuitivement un triangle est à peu près la moitié d'un carré, et dans Big-O notation des constantes peut être ignoré si O (n ^ 2) est le résultat attendu.

Answer 3

La solution est assez facile pour celui-ci. Vous devez déroulez la récursion:

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 

Vous avez ici progression arithmétique et la somme est 1/2*n*(n-1). Techniquement il vous manque la condition limite, mais avec une condition limite constante que vous voyez que la récursion est O(n^2).

Answer 4

semble correcte, mais dépend du cas de base T (1). En supposant que vous ferez n étapes pour obtenir T (n) à T (0) et chaque fois que le terme n est nulle part entre 0 et n pour une moyenne de n / 2 si n * n / 2 = (n ^ 2) / 2 = O (n ^ 2).