Como resolver a recorrência.T (n).= T (N-1) + T (N / 2) + N?

Question

Estou ciente de que para obter um tempo de execução pelo método da árvore de recursão, precisamos desenhar uma árvore e encontrar:

a) Número de níveis na árvore .

Desde o lado esquerdo da árvore diminui por 1 em tamanho, então é o caminho mais longo da raiz. Tamanho do subproblema no nível i é n-i. Configuração n - i= 1 Quando atinge um tamanho de 1, obtemos o número de níveis, i= n - 1.

b) Custo por nó na árvore : cn

c) Número de nós no nível I : é aqui que estou preso. Não é possível encontrar nós no nível i Desde o lado esquerdo diminui em 1, lado direito pela metade. Naturalmente, a árvore é mais densa para o lado esquerdo. Nem todo nó terá dois filhos.

Se eu puder obter resposta para c, eu posso calcular t (n)= custo do nível 0 + custo do nível 1 + custo do nível 2 + ... custo do nível N-1. Se y1 é o número de nós no nível 1, Y2 no nível 2, etc ... então
=> T (n)= cn + y1 * cn + y2 * cn + y3 * cn + .... yn-1 * cn para obter custo total.

Alguém pode me guiar para a abordagem que estou tomando? está correto ? Posso assumir uma suposição de que, por n / 2 suficientemente grande, podemos ignorar T (N / 2) e, em seguida, proceder? .

Online Pesquisando me confundiu. O problema é 4,4-5 dos CLRS.

Por favor, veja aqui

Esta solução diz t (n)= o (2 ^ n) e t (n)= ômega (n ^ 2) e não explica como.

também ver aqui

Esta solução diz t (n)= o (n ^ 2). mas contradiz com a solução acima

Answer 1

Deixe $ s (n)= t (n) - 2n - 2 $ . Você pode verificar se $ s (n)= s (n-1) + s (n / 2) $ (ignorando o fato de que $ n / 2 $ não precisa ser um inteiro). Isso mostra que o aditivo $ n $ termo não faz uma grande diferença.

para grande $ n $ , temos aproximadamente $ s (n) - s (n-1) \ aprox. S '(n) $ , e por isso somos levados a resolver a equação diferencial $$ S '(n)= s (n / 2). $$ Considere $ f (n)=exp (\ tfrac {1} {2} \ log_2 ^ 2 n) $ . Então $$ f '(n)=exp (\ tfrac {1} {2} \ log_2 ^ 2 n) \ cdot \ frac {\ ln n} {(\ ln 4) n}, $$ enquanto $$ f (n / 2)=exp (\ tfrac {1} {2} (\ log_2 n - 1) ^ 2) \ APROX \ Exp (\ TFRAC {1} {2} \ log ^ 2 n) \ exp ( - \ log n)=exp (\ tfrac {1} {2} \ log ^ log ^ \ 2 n) \ cdot \ frac {1} {n}. $$ Isso sugere que, no mínimo, $ \ ln s (n)=theta (\ log ^ 2 n) $ .

De onde vem isso? Você pode pensar em $ s (n) $ (com uma caixa de base apropriada!) Como o número de maneiras de ir de $ n $ para zero aplicando duas operações: subtrair 1 e dividir por 2. Uma sequência "típica" conterá aproximadamente $ \ log_2n $ muitas operações do segundo tipo, fora de $ \ theta (n) $ Operações no total, levando à estimativa muito áspera $ \ binom {\ theta (n)} {\ log_2 n} $ , que também é do formulário $ \ exp \ theta (\ log ^ 2 n) $ .

---

.

Considere para a concretude a seguinte definição precisa de $ s (n) $ : A caixa de base é $ S (0 )= 1 $ , e para $ n> 0 $ , $$ S (n)= s (n-1) + s (\ lFloor n / 2 \ rfloor). $$ Esta é a sequência A000123 . Knuth, uma recorrência quase linear , mostrou que $$ \ log_4 s (n) \ sim \ log_4 ^ 2 n, $$ Ou seja, a proporção dos dois termos tende a 1 como $ n \ to \ infty $ . A entrada do OEIS contém assimptotics ainda mais precisas.

Answer 2

Eu discordo da hipnose de fibonacci, mas não tenho cem por cento de certeza da minha resposta

você vê $ t (n)= t (n-1) + c * n= O (n ^ 2) $

$ t (n)= t (n / 2) + c * n= o (n log n) $

No entanto, você não recebe ur t (n) por adição direta.

Se você for um nível na recursão (vc pode desenhar uma árvore)

t (n)= T (N-2) + T ((N-1) / 2) + T (N / 2-1) + T (N / 4) + [N + (N-1) + (N-1) / 2 + (N / 2-1) + N / 4]

isto para mostrar u também não é apenas $ o (n ^ 2) $

Eu tenho que completá-lo, mas suspeito de $ o ((n ^ 2) * log n) $ ou $ o ((n ^ 2) * n ^ {log n})= O (n ^ 3) $

{há um termo n (1 + 1/2 + 1/4 + .. 1 / n) que se decai em log n etapas, tenho que verificar novamente}