Comment résoudre la complexité récursive de t (n) = t (n / 2) + 2 ^ n par méthode d'itération?

Question

J'essaie de trouver la limite supérieure et la borne inférieure, qui est probablement o (2 ^ n)

T (n) = 1 pour n <= 4

Je sais que l'orgue général est:

T (n) = t (n / 2 ^ (i + 1)) + somme de i = 0 à k de 2 ^ (n / 2 ^ i)

---

De là, je ne sais pas comment continuer.

Answer 1

Il y a un problème avec votre notation. L'orgue général devrait être:

T(n) = T(n/2^(i+1)) + sum from k=0 to i of 2^(n/2^k)

Après cette étape, nous laissons i = log(2, n) - 1, pour que T(n/2^(i+1)) = T(1).

Par conséquent, T(n) = T(1) + sum from k = 0 to (log(2, n) - 1) of 2^(n/2^k).

Notez que sum from k = 0 to (log(2, n) - 1) of 2^(n/2^k) est 2^n + 2^(n/2) + 2^(n/4) + ..., qui est plus petit que 2^n + 2^(n-1) + 2^(n-2) + .... Cependant, ce dernier truc est 2^(n+1) - 1. Donc, les anciens trucs sont quelque chose entre 2^n et 2^(n+1). Par conséquent, la somme est O(2^n).

Alors T(n) = O(2^n).