La détermination Bigo d'une récidive

Question

T (1) = c    
T (n) = T (n/2) + dn

Comment puis-je déterminer Bigo de ce rapidement?

Answer 1

L'utilisation répétée backsubstitution et trouver le motif. Un exemple .

Answer 2

Je ne suis pas tout à fait sûr de ce que dn est, mais en supposant que vous dire une constante multipliée par n:

Selon Wolfram Alpha , la solution de l'équation de récurrence pour:

f(n) = f(n / 2) + cn

est:

f(n) = 2c(n - 1) + c1

ce qui en ferait O(n).

Answer 3

Eh bien, la partie de récurrence de la relation est le T (n / 2) fait partie, qui est en effet de réduire de moitié la valeur de n à chaque fois.

Ainsi, vous aurez besoin d'environ. (Log2 n) les étapes pour arriver à la condition de cessation d'emploi, d'où le coût global de l'algorithme est O (log2 n). Vous pouvez ignorer la partie dn tout comme une opération à temps constant pour chaque étape.

Notez que comme indiqué, le problème ne sera pas nécessairement fin puisque la réduction de moitié d'une valeur arbitraire de n est peu probable à plusieurs reprises de frapper exactement 1. Je pense que la partie T (n / 2) devrait effectivement lire T (étage (n / 2)) ou quelque chose comme ça pour faire en sorte que ce termine.

Answer 4

utilise le théorème de maître voir http://en.wikipedia.org/wiki/Master_theorem

Par ailleurs, le comportement asymptotique de votre récurrence est O (n) dans l'hypothèse d est positive et suffisamment inférieure à n (taille du problème)