خوارزميةاحترافي
العَوْدية: شجرة استدعاءات فيبوناتشي
استدعاءان عَوْديان في كل خطوة يُنميان شجرة من الاستدعاءات، ويكشفان عملاً مكرّراً كثيراً.
- الزمن
- O(2ⁿ)
- الذاكرة
- O(n)
تتبّعها خطوة بخطوة
الخطوة 1 من 13
1function fib(n) {2 if (n <= 1) return n;3 return fib(n - 1) + fib(n - 2);4}- calls
- = 1
- fib(4)
نستدعي fib(4). يحتاج أولاً إلى fib(3) و fib(2).
درس احترافي
افتح الشرح الكامل
هذا الدرس جزء من الخطة الاحترافية، التي تفتح كل خطوة في كل درس، إضافة إلى تدريبات الأنماط وتقارير الإتقان.
اطّلع على الأسعاركيف تعمل
يستدعي fib(n) كلاً من fib(n − 1) و fib(n − 2)، فتتفرّع الاستدعاءات على شكل شجرة. ينتظر كل استدعاء عودة ابنيه ثم يجمع نتيجتيهما. دقّق النظر وسترى المسائل الفرعية نفسها تتكرّر: حتى مع n = 4 يُحسب fib(2) مرتين، وتتضاعف الشجرة تقريباً مع كل زيادة في n. هذا زمن O(2ⁿ). البرمجة الديناميكية تحلّ ذلك بتذكّر الإجابات.
تدرّب على اكتشاف هذا النمط →