Melhor maneira de lidar com pisos e tetos ao usar o método de substituição para resolver Recorrências

5

Atualmente, estou usando o método de substituição para resolver as recorrências. O problema que estou tendo é lidar com T (n) que têm tetos ou pisos. Por exemplo, no exemplo a seguir veja o exemplo aqui .

Eles acabam usando o palpite: T(n) ≧ c(n+2) lg(n+2)

Meu primeiro palpite foi T(n) ≧ n lg(n) , que acabou não funcionando, mas meu problema é que eu acabo tendo que brincar com o palpite para tentar fazer com que um funcione. Então, as perguntas são as seguintes:

  1. Qual é a melhor maneira de lidar com esses pisos e teto em geral?
  2. Com relação a adivinhações, isso vem com a prática ou existem maneiras melhores de deduzir a suposição correta do primeiro disparo sem ter que usar árvores de recursão.

(PS não sabe como escrever equações em notação matemática, é minha primeira vez usando este fórum)

    
por user481610 27.08.2014 / 21:55
fonte

1 resposta

1

Na tentativa de responder à questão 2, gostaria de citar o seguinte

Ultimately, there is only one fail-safe method to solve any recurrence:

Guess the answer, and then prove it correct by induction.

Por favor, confira o seguinte link - link .Este descreve técnicas para gerar estimativas que sejam garantidas como corretas, desde que você as use corretamente. Já faz algum tempo que fiz algo nesse sentido, mas também acho que seguir um processo em um livro, como sugerido por Andrew, é a melhor solução, já que não é algo que possa ser rapidamente descrito em um post no fórum.

    
por 09.01.2015 / 07:50
fonte

Tags