Recursão Árvore, Resolvendo equações de recorrência

Question

Tanto quanto eu sei Há 4 maneiras de resolver equações de recorrência: 1- árvores recursão 2- Substituição 3 - A iteração 4 - Derivado

Somos convidados a usar Substituição, que teremos de adivinhar uma fórmula para a saída. Eu li a partir CLRS livro que não há mágica para fazer isso, eu estava curioso para saber se há alguma heurística para fazer isso?

Eu posso certamente tem uma idéia desenhando uma árvore recorrência ou usando iteração, mas, porque a saída será em formato Theta Big-OH ??ou, fórmulas does not necessariamente corresponder.

Será que qualquer um tem alguma recomendação para a resolução de equações de recorrência utilizando a substituição?

Answer 1

Para os simples, basta dar uma estimativa "razoável".

Para os mais complicados, eu iria em frente e usar uma árvore de recorrência - parece-me ser o mais fácil "algoritmo" para gerar um palpite. Note-se que pode ser difícil de usar uma árvore de recorrência para provar um limite (os detalhes são difíceis de obter direita). árvores de recorrência são altamente úteis para a formação de suposições que são então provadas por substituição.

Eu não sei por que você está dizendo as fórmulas não irá coincidir com a saída no Big-O ou Theta. Eles normalmente não correspondem exatamente, mas isso é parte do ponto de Big-O. Parte do truque de volta para substituição vai é saber como ligar a solução Big-O para fazer o trabalho para fora substituição álgebra. IIRC, CLRS funciona fora um ou dois exemplos disso.

Answer 2

Por favor, note que a lista de possíveis maneiras de resolver equações de recorrência definitivamente não é completo, seu meramente um conjunto de ferramentas que ensinam cientistas da computação, porque eles provavelmente irá resolver a maioria dos seus problemas.

Para soluções exatas das equações de recorrência matemáticos usam uma ferramenta chamada funções geradoras. funções geradoras dar-lhe soluções exatas, e em geral são mais poderosos do que o teorema de mestre.

Há um grande recurso on-line para aprender sobre a aqui. http://www.math.upenn.edu/~wilf/DownldGF.html

Se você percorrer os primeiros exemplos de um par você deve pegar o jeito dele em nenhum momento.

Você precisa de algum fundo de matemática e entender série de Taylor rudimentar. http://en.wikipedia.org/wiki/Taylor_series

funções geradoras são também extremamente útil na probabilidade.