La complexité de la récurrence: T(n) = T(n-1) + T(n-2) + C

Je veux comprendre comment arriver à la complexité de la relation de récurrence.

T(n) = T(n-1) + T(n-2) + C
Compte tenu de T(1) = C et T(2) = 2C;

Généralement pour les équations comme T(n) = 2T(n/2) + C (Donnée T(1) = C), j'utilise la méthode suivante.

T(n) = 2T(n/2) + C
=> T(n) = 4T(n/4) + 3C
=> T(n) = 8T(n/8) + 7C
=> ...
=> T(n) = 2^k T (n/2^k) + (2^k - 1) c

Maintenant, quand n/2^k = 1 => K = log (n) (à la base 2)

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

Mais, je ne suis pas en mesure de venir avec une approche similaire pour le problème que j'ai en question. S'il vous plaît corrigez-moi si mon approche est incorrecte.

OriginalL'auteur Gopal | 2013-07-18

6

La complexité est liée à l'entrée de la taille, où chaque appel de produire un binaire-l'arbre des appels

Où T(n) faire 2ⁿ appels au total.

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

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

O(2ⁿ)

De la même manière, vous pouvez généraliser votre fonction récursive, comme un nombre de Fibonacci

T(n) = F(n) + ( C * 2ⁿ)

Ensuite, vous pouvez utiliser une formule directe au lieu de récursive façon

À l'aide d'une méthode complexe connu comme La Formule de Binet

OriginalL'auteur Khaled.K
4

Vous pouvez utiliser cette approche générale décrite ici.Veuillez vous demander si vous avez plus de questions.

lien que vous avez fourni est d'une grande aide!

OriginalL'auteur Aravind
4

Est "pire que exponentiel" assez précis pour vos besoins? Le cas particulier C=0 définit http://en.wikipedia.org/wiki/Fibonacci_number, que vous pouvez voir à partir de l'article est exponentielle. En supposant que C est positif, votre série sera augmente plus rapidement que cela. En fait, votre série sera entre de la suite de Fibonacci, et une variante de la suite de Fibonacci dans lequel le nombre d'or est remplacé par quelque chose de très légèrement plus grand.

pour la réponse rapide!

OriginalL'auteur mcdowella

Si vous êtes aussi intéressé à trouver une formule explicite pour T(n) cela peut aider.

Nous savons que T(1) = c et T(2) = 2c et T(n) = T(n-1) + T(n-2) + c.

Donc il suffit d'écrire T(n) et début expansion...

T(n) = T(n-1) + T(n-2) + c
T(n) = 2*T(n-2) + T(n-m) + 2c
T(n) = 3*T(n-3) + 2*T(n-4) + 4c
T(n) = 5*T(n-4) + 3*T(n-5) + 7c
etc ...

Vous voyez les coefficients sont des nombres de Fibonacci eux-mêmes!

Appel F(n) la nth nombre de Fibonacci. F(n) = (phi^n + psi^n)/sqrt(5) où phi = (1+sqrt(5))/2 et psi = -1/phi, alors nous avons:

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

Voici quelques rapide de code pour illustrer:

def fib_gen(n):
    """generates fib numbers to avoid rounding errors"""
    fibs=[1,1]
    for i in xrange(n-2):
        fibs.append(fibs[i]+fibs[i+1])
    return fibs

F = fib_gen(50) #just an example.
c=1

def T(n):
    """the recursive definiton"""
    if n == 1:
        return c
    if n == 2:
        return 2*c
    return T(n-1) + T(n-2) + c

def our_T(n): 
    n=n-2 #just because your intials were T(1) and T(2), sorry this is ugly!
    """our found relation"""
    return F[n]*2*c + F[n-1]*c + (F[n+1]-1)*c

>>> T(24)
121392
>>> our_T(24)
121392

OriginalL'auteur seth

0

Ce type de récidives sont appelés: non-homogène des relations de récurrence et vous avez à résoudre dans le début homogène de récidive (l'un sans une constante à la fin). Si vous êtes intéressé, lisez les mathématiques derrière elle.

Je vais vous montrer un moyen facile. Il suffit de saisir votre équation dans wolfram-alpha et vous obtiendrez:

Donc la complexité augmente de la même manière comme Lucas ou le nombre de Fibonacci (le plus grand d'entre eux).

Mais tous les deux ont le même taux de croissance:

et, par conséquent, le taux de croissance est exponentielle du nombre d'or: O(phi^n)

OriginalL'auteur Salvador Dali

Vous devez vous connecter pour publier un commentaire.