La Récursivité De L'Arbre, De La Résolution Des Équations De Récurrence

Question

Autant que je sache, Il y a 4 façons de résoudre les équations de récurrence :1 - la Récursivité des arbres 2 - la Substitution 3 - Itération 4 - Dérivés

Nous sommes invités à utiliser de Substitution, dont nous aurons besoin pour deviner une formule pour la sortie.J'ai lu de PLC livre qu'il n'y a pas de magie pour ce faire, j'ai été curieux de savoir si il existe des heuristiques pour ce faire?

Je peux certainement avoir une idée de dessin d'une récurrence de l'arbre ou de l'utilisation de l'itération, mais, parce que la sortie sera en Grande-OH ou Thêta format, les formules ne marche pas nécessairement de correspondance.

Ne tout on a une recommandation pour la résolution des équations de récurrence à l'aide de la substitution?

Answer 1

Pour de plus simple, il suffit de prendre un "raisonnable" deviner.

Pour les plus compliqués, je voudrais aller de l'avant et utiliser une récurrence de l'arbre—, il me semble être le plus facile "algorithme" pour générer une supposition.Notez qu'il peut être difficile d'utiliser une récurrence de l'arbre de prouver une borne (les détails sont difficiles à obtenir à droite).La récurrence des arbres sont très utiles pour former des conjectures qui sont ensuite prouvé par substitution.

Je ne suis pas sûr de savoir pourquoi vous dites que les formules ne correspond pas avec la sortie en Grande-O ou Thêta.En général, ils ne correspondent pas exactement, mais c'est la partie de la pointe de Grande-O.Une partie de l'astuce de revenir à la substitution, c'est de savoir comment brancher le Big-O solution pour faire de la substitution de l'algèbre travail.IIRC, PLC fonctionne un exemple ou deux de ce.

Answer 2

Veuillez noter que la liste des moyens de résoudre les équations de récurrence n'est certainement pas complet, sa simplement un ensemble d'outils qu'ils enseignent Ordinateur Scientifiques, parce qu'ils seront plus susceptibles de résoudre la plupart de vos problèmes.

Pour des solutions exactes des équations de récurrence mathématiciens utilisent un outil appelé fonctions génératrices.Fonctions génératrices vous donner des solutions exactes, et, en général, sont plus puissants que le maître théorème.

Il est une excellente ressource en ligne pour apprendre le ici. http://www.math.upenn.edu/~wilf/DownldGF.html

Si vous passez par les deux premiers exemples, vous devriez obtenir le blocage de celui-ci en un rien de temps.

Vous avez besoin d'une formation en mathématiques et comprendre rudimentaire de la série de taylor. http://en.wikipedia.org/wiki/Taylor_series

Fonctions génératrices sont également très utile en probabilité.