Méthode de substitution

Question

Je voulais juste vérifier certaines choses que j'ai fait les étapes ci-dessous non?

T(n) = 3T(n/3) + n : Theta(nlogn) 

O(nlogn) 

T(k) = cklog(k) k<n 

T(n/4) = c(n/3)log(n/3) 
     = c(n/3)[logn - log3] 
     = c(n/3)logn - c(n/3)log3  

T(n) = cnlogn-cnlog3 + n 

     <= cnlogn -cn + n 
     <= cnlogn -dn **[STEP A]** 
     <= cnlogn if c >= d 

Omega(nlogn) 
    >= cnlogn -cn + n 
    >= cnlogn -dn **[STEP A]** 
    >= cnlogn if 0 < c <= d 

Je ne parviens pas à l'étape A ce que je fini mes gammes de c était:

c> = 1 pour la limite supérieure c < = 1 pour la limite inférieure

Existe-t-il une raison particulière pour laquelle vous associeriez cn + n. Je peux en quelque sorte voir la logique derrière cela, mais est-il nécessaire de faire cette étape? Parce que je peux faire pour que tous les cas ... ce qui est un peu bizarre ..

Answer 1

Vous étiez encore droit jusqu'à ce que:

T(n) = cnlogn-cnlog3 + n 
    >= cnlogn -cn + n 

pour Ω(nlogn)

car il ne vaut que pour c < = 0, ce qui est contradictoire avec notre hypothèse que c> = 0.

Une façon de fixer la deuxième preuve pourrait être:

T(n) = cnlogn - cnlog3 + n 
    = cnlogn - n(clog3 - 1) 
    <= cnlogn when c >= 1/log3 

Par conséquent: T(n) = Ω(nlogn).

En général, les valeurs de la borne inférieure et de la borne supérieure importent peu. Le but est de trouver deux constantes c1 et c2 telles que:

c1*n*logn <= T(n) <= c2*n*logn pour n >= some n0.