La Recursividad Árbol, La Resolución De Ecuaciones En Recurrencia

Question

Que yo sepa Hay 4 maneras de resolver ecuaciones en recurrencia :1 - la Recursividad de los árboles 2 - Sustitución de 3 - Iteración 4 - Derivados

Se nos pide el uso de la Sustitución, que tendremos que adivinar una fórmula para la salida.He leído de CLRS libro que no hay magia para hacer esto, tenía curiosidad por saber si hay alguna heurística para hacer esto?

Sin duda, puedo tener una idea mediante el dibujo de una recurrencia del árbol o el uso de iteración, pero, debido a que la salida será en Grande-OH o Theta formato, fórmulas no necesariamente coinciden.

¿Alguno tiene alguna recomendación para la resolución de ecuaciones en recurrencia por medio de la sustitución?

Answer 1

Para los más sencillos, acaba de tomar una "razonable" adivinar.

Para obtener más complicados, me gustaría ir por delante y el uso de una recurrencia del árbol — a mí me parece la más fácil "algoritmo" para la generación de una conjetura.Tenga en cuenta que puede ser difícil el uso de la recurrencia de árbol para probar un atado (los detalles son difíciles de conseguir a la derecha).La recurrencia de los árboles son de gran utilidad para la formación de conjeturas que luego son probadas por sustitución.

No estoy seguro de por qué usted está diciendo que las fórmulas no coincidir con la salida en Big-O o Theta.Por lo general, no coinciden exactamente, pero eso es parte de el punto de Big-O.Parte del truco de volver a la sustitución es saber cómo conectar el Big-O solución para hacer la sustitución de álgebra de trabajo a cabo.Si mal no recuerdo, CLRS sí hace una o dos ejemplos de esto.

Answer 2

Por favor, tenga en cuenta que la lista de posibles formas de resolver ecuaciones en recurrencia no es, definitivamente, completo, sus meramente un conjunto de herramientas que enseñar a los Científicos de la computación, porque lo más probable es resolver la mayoría de sus problemas.

Para las soluciones exactas de ecuaciones en recurrencia matemáticos uso de una herramienta llamada generación de funciones.La generación de las funciones de dar soluciones exactas, y en general son más poderosos que el maestro teorema.

No es un gran recurso en línea para aprender sobre el aquí. http://www.math.upenn.edu/~wilf/DownldGF.html

Si usted va a través de los dos primeros ejemplos que usted debe conseguir la caída de ella en ningún momento.

Usted necesita un poco de matemática de fondo y entender rudimentaria serie de taylor. http://en.wikipedia.org/wiki/Taylor_series

Funciones de generación son también muy útil en la probabilidad.