Considérons, T (n) = aT (n/b) + n^c pour n> 1
Il y a trois cas (note que b est la base du journal)
(1) if logb a < c, T(n)=Θ(n^c),
(2) if logb a = c, T (n) = Θ(n^c log n),
(3) if logb a > c, T(n) = Θ(n^(logb a)).
Dans votre cas, vous avez
T(n) = T(2n/3) + n^0
On peut dire,
n^0 here because Θ(1) = Θ(n^0)
Ainsi,
a = 1, b = 3/2, and c = 0
Nous pouvons verity facilement que
log3/2 1 = 0
Ainsi, nous voyons que nous devons utiliser le cas 2
logb a = c
Ainsi,
T(n) = Θ(n^c log n) = Θ(n^0 log n) = Θ(log n)
En regardant l'image que vous avez publié
Observer cas 2.
Il dit que
Θ(n log n) if d = b
En est générale,
Θ(n^i log n) if d = b^i
d = b^i implies logb d = i
Mais pour des raisons de (normalement) la clarification
d = 1 et b = 3/2 (et comme illustré ci-dessus) i = 0
Ainsi,
d = b^i est vrai
J'ai utilisé des lettres différentes ici mais c'est identique à la façon dont j'ai décrit ci-dessus. J'ai fait la même chose deux fois, une fois en utilisant les lettres dans votre message pour espérer éclaircir les choses pour vous. Peu importe comment vous voulez le regarder, vous utiliseriez le cas 2.
Regardez votre relation de récurrence et comparez-la à la forme générale donnée dans le lien. Vous devriez être capable de déduire 'b, c, d' de là. 'a' n'a pas d'importance parce que c'est seulement une constante additive. – meowgoesthedog
@meowgoesthedog ce n'est pas un lien vers [Master theorm] (https://en.wikipedia.org/wiki/Master_theorem_ (analysis_of_algorithms)) mais un lien vers une image. OP, essayez de lire le lien dans mon commentaire. –
donc, b est 3/2, d est 1. d