Como representar uma recorrência que incrementa por um em cada nível de árvore?

Question

Eu estou usando um tipo de mesclagem como algoritmo.Cada nível da árvore tem um grande tempo de execução diferente.O tempo de execução como um todo pode representar a seguinte forma:

$$ O (\ SUM_ {I= 0} ^ {log (n)} 2 ^ {\ frac {n} {2 ^ i}} * 2 ^ i)$$

Estou tentando encontrar a recorrência.Como isso é como Mesclar Classe, podemos começar com o clássico 2T (N / 2).No entanto, não tenho certeza de como escrever o que vem depois de 2T (n / 2) na recorrência abaixo: $$ T (n)= 2T (N / 2) + O (2 ^{\ frac {n} {2 ^ i}} * 2 ^ i) $$ i ++ Cada recorrência

Estou ciente de que este é o tempo exponencial.Minha suposição é que tudo isso simplifica para o (2 ^ n).É essa suposição correta?

BOGO SORT + MERGE SORT exemplo .

Answer 1

À medida que cada vez $ n $ é dividido por $ 2 $ e $ 2 $ multiplicado por 2, deve ser: $$ T (n)= 2t (\ frac {n} {2}) + 2 ^ n $$ Agora, se você expandir:

$$ T (n)= 2 (t (\ frac {n} {2 ^ 2}) + 2 ^ {\ frac {n} {n} {2}}) + 2}}) + 2 ^ n= 2t (\ frac {n} {2} }) + 2 \ vezes 2 ^ {\ frac {n} {2}} + 2 ^ n $$

Como podemos adivinhar $ t (\ frac {n} {2}) $ ? Porque $ i $ está mudando de $ 0 $ para $ \ log {n} $ . Se supometos $ t (0) $ , quando $ i= 0 $ , será o não parte recorrente da equação. Assim, descobrimos que é $ 2 ^ n $ . Como encontramos que deveríamos multiplicar por $ 2 $ ? Porque cada vez que a relação é multiplicada pela $ 2 $ e temos um poder dele em cada iteração. Assim, deve ser multiplicado pela parte recorrente da relação, que é $ t (\ frac {n} {2}) $ aqui.

Eventualmente, formar o teorema de materso, podemos concluir que $ t (n)=theta (2 ^ n) $ .