شجرة العودية، حل معادلات تكرار

Question

بقدر ما أعرف أن هناك 4 طرق لحل المعادلات المتكررة: 1- الأشجار العودية 2- الاستبدال 3 - التكرار 4 - مشتق

يطلب منا استخدام الاستبدال، والتي سنحتاج إلى تخمين صيغة للإخراج. قرأت من كتاب CLRS أنه لا يوجد سحر للقيام بذلك، كنت فضوليا إذا كان هناك أي من الاستدلال للقيام بذلك؟

بالتأكيد يمكن أن يكون لدي فكرة عن طريق رسم شجرة تكرار أو استخدام التكرار ولكن، لأن الإخراج سيكون بتنسيق كبير أوه أو ثيتا، لا تتطابق الصيغ بالضرورة.

هل لدى أي شخص أي توصية لحل المعادلات المتكررة باستخدام الاستبدال؟

Answer 1

بالنسبة إلى بسيطة، فقط خذ تخمين "معقول".

لأكثر تعقيدا، سأضي قدما واستخدم شجرة تكرار - يبدو لي أن أكون أسهل الخوارزمية "لتوليد تخمين. لاحظ أنه قد يكون من الصعب استخدام شجرة تكرار لإثبات ملزمة (التفاصيل صعبة للحصول على حق). الأشجار المتكررة مفيدة للغاية لتشكيل التخمينات التي أثبتت بعد ذلك عن طريق الاستبدال.

لست متأكدا من السبب في أنك تقول أن الصيغ لن تتطابق مع الإخراج في Big-O أو Theta. عادة لا تتطابق بالضبط، لكن هذا جزء من نقطة Big-O. جزء من خدعة العودة إلى الاستبدال يعرف كيفية توصيل الحل Big-o لجعل الجبر الاستبدال يعمل. IIRC، تقوم CLRS بعمل مثال أو اثنين من هذا.

Answer 2

يرجى ملاحظة أن قائمة الطرق الممكنة لحل المعادلات المتكررة لا تكتمل بالتأكيد، وهي مجرد مجموعة من الأدوات التي تعلمها علماء الكمبيوتر، لأنهم من المرجح أن يحلوا معظم مشاكلك.

بالنسبة للحلول الدقيقة من معادلات التكرار، يستخدم علماء الرياضيات أداة تسمى توليد الوظائف. تمنحك وظائف توليد الحلول الدقيقة، وبشكل عام أقوى من نظرية السيد.

هناك مورد رائع عبر الإنترنت للتعرف على هنا. http://www.math.upenn.edu/~wilf/downldgf.html.

إذا ذهبت من خلال أمثلة الزوجات الأولى، يجب أن تحصل على تعليق منه في أي وقت من الأوقات.

تحتاج إلى بعض خلفية الرياضيات وفهم سلسلة تايلور البدائية. http://en.wikipedia.org/wiki/taylor_series.

وتولد الوظائف هي أيضا مفيدة للغاية في الاحتمال.