La Relation de récurrence: la Résolution de Grand O de T(n-1)

Je suis à la résolution de certains par la relation de récurrence des problèmes pour Big O et jusqu'à présent, jusqu'à ce point ont rencontré des relations de récurrence qui participe de cette forme:

T(n) = a*T(n/b) + f(n)

Pour le haut, c'est assez facile pour moi de trouver le Big O la notation. Mais j'ai récemment jeté une balle courbe avec l'équation suivante:

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

Je ne suis pas vraiment sûr de savoir comment aller autour de la résolution de ce pour Big O. en fait, j'ai essayé de le brancher dans l'équation suivante:

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

Je ne suis pas entièrement sûr si cela est correct, mais je suis coincé et ont besoin d'un peu d'aide. Merci!

InformationsquelleAutor Parth | 2010-07-11
  1. 17

    En Supposant Que T(1) = 0

    T(n) = T(n-1) + 2
 = (T(n-2) + 2) + 2
 = T(n-2) + 4
 = (T(n-3) + 2) + 4
 = T(n-3) + 6
 = T(n-k) + 2k

    Ensemble k à n-1 et que vous avez

    T(n) = 2n - 2

    Par conséquent, il est O(n)

    • vous avez eu un message d'erreur sur votre dernière ligne, j'ai édité
    • oh, oui, je le savais! merci!
    • Je n'ai pas suivi vos algèbre sur les deux premières étapes. Vous prétendez que $T(n-1) + 2 = (T(n-2) + 2) + 2$, mais je ne vois pas comment vous arrivez à cette conclusion. Rien dans le problème des allusions à cette alors, comment pouvez-vous faire de cette hypothèse? Si $T(2) = 10000000000000000$ nous ne savons pas alors comment pouvez-vous supposer qu'il ne l'est pas?
    • Si nous plug in (n-1) dans l'original T(n), nous obtenons, T(n-1) = T(n-2) + 2. Droit? Maintenant, si on remplace T(n-1) sur la première ligne avec T(n-2)+2 nous obtenons la deuxième ligne.
    InformationsquelleAutor Andreas Jansson
  2. 1

    Depuis que la question est déjà une réponse, permettez-moi d'ajouter une certaine intuition derrière comment trouver la complexité de la récurrence.

    • Maître théorème ne s'applique qu'à la diviser et conquérir type de récidives, comme T(n) = a*T(n/b) + f(n) où a est le nombre de sous-problèmes, et chacun de ces subproblem taille 1/b du problème original. Mais la récurrence T(n) = T(n-1) + 2 n'est techniquement pas "diviser" le problème en sous-problèmes. maître théorème ne s'applique pas ici.
    • Si l'on veut bien regarder la récidive, il est assez clair qu'il va au-dessus de n étapes et à chaque pas de temps constant, ce qui est 2 dans ce cas. Donc, la complexité serait O(n).

    Surtout je trouve la deuxième intuition très utile pour la plupart des récidives (peut être pas tous). Comme un exemple, vous pouvez essayer la même pour un même récurrence T(n) = T(n-1) + n, dont la complexité est, bien sûr, O(n^2).

    InformationsquelleAutor Nasir
  3. 0

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

    Donc T(n) = 2*n ce qui implique O(n)

    InformationsquelleAutor Chaos