trouver la complexité temporelle de la relation de récurrence dans les algorithmes

T (n) = 1 si n < = 0 T (n) = T (n-1) + T (n-2) + n

2010-09-24 sudh

Quels sont vos cas de base? n <= 0? – AlcubierreDrive

zéro des réponses acceptées et zéro des upvotes? pas d'accord –

Selon OEIS, la formule fermée pour cette fonction est , ce qui signifie que la complexité asymptotique de cette fonction est alt text .

2010-09-25 12:12:47 svick

Tenir compte

F(n) = T(n) + n + 3.

Cela nous donne

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

i.e 

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

i.e 

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

qui est une séquence de Fibonacci comme!

Il est bien connu que pour les séquences de type fibonacci, F(n) = Theta(phi^n) où phi est le nombre d'or.

2010-09-25 22:46:42

Je suis d'accord avec la conclusion, mais je pense que la preuve est fausse: la partie "i.e." est incorrecte. – svick

@Svick: C'est l'arithmétique de base! Je n'ai pas dit que c'était la séquence _the_ fibonacci. Les termes sont différents. –

@Moron: Oui, c'est de l'arithmétique basique, mais '(n + 1)! = (N-1)' et vous ne pouvez pas ignorer ça. – svick

Répondre