العودية هو مفهوم أساسي في علوم الكمبيوتر والرياضيات يسمح للوظائف بتسمية نفسها، مما يتيح حل المشكلات المعقدة من خلال خطوات متكررة. أحد التمثيلات المرئية المستخدمة بشكل شائع لفهم وتحليل تنفيذ الوظائف العودية هو شجرة العودية. في هذه المقالة، سنستكشف النظرية الكامنة وراء الأشجار العودية وبنيتها وأهميتها في فهم الخوارزميات العودية.
ما هي شجرة العودية؟
شجرة العودية هي تمثيل رسومي يوضح تدفق تنفيذ وظيفة العودية. وهو يوفر تحليلاً مرئيًا للاستدعاءات العودية، ويعرض تقدم الخوارزمية أثناء تفرعها ووصولها في النهاية إلى الحالة الأساسية. يساعد هيكل الشجرة في تحليل التعقيد الزمني وفهم العملية العودية المعنية.
هيكل الشجرة
تمثل كل عقدة في شجرة العودية مكالمة متكررة معينة. يتم عرض المكالمة الأولية في الأعلى، مع تفرع المكالمات اللاحقة أسفلها. تنمو الشجرة للأسفل لتشكل هيكلًا هرميًا. يعتمد عامل التفرع لكل عقدة على عدد الاستدعاءات العودية التي يتم إجراؤها داخل الوظيفة. بالإضافة إلى ذلك، يتوافق عمق الشجرة مع عدد الاستدعاءات العودية قبل الوصول إلى الحالة الأساسية.
الحالة الأساسية
تعمل الحالة الأساسية كشرط إنهاء لوظيفة متكررة. يحدد النقطة التي يتوقف عندها العودية وتبدأ الدالة في إرجاع القيم. في شجرة العودية، عادةً ما يتم تصوير العقد التي تمثل الحالة الأساسية على أنها عقد ورقية، لأنها لا تؤدي إلى مزيد من الاستدعاءات العودية.
المكالمات العودية
تمثل العقد الفرعية في شجرة العودية الاستدعاءات العودية التي يتم إجراؤها داخل الوظيفة. تتوافق كل عقدة تابعة مع استدعاء متكرر منفصل، مما يؤدي إلى إنشاء مشاكل فرعية جديدة. قد تختلف القيم أو المعلمات التي تم تمريرها إلى هذه الاستدعاءات العودية، مما يؤدي إلى اختلافات في خصائص المسائل الفرعية.
تدفق التنفيذ:
يوفر اجتياز شجرة العودية نظرة ثاقبة لتدفق تنفيذ وظيفة العودية. بدءًا من الاستدعاء الأولي عند العقدة الجذرية، نتبع الفروع للوصول إلى الاستدعاءات اللاحقة حتى نواجه الحالة الأساسية. عند الوصول إلى الحالات الأساسية، تبدأ الاستدعاءات العودية في العودة، ويتم تمييز العقد الخاصة بها في الشجرة بالقيم التي تم إرجاعها. يستمر الاجتياز حتى يتم اجتياز الشجرة بأكملها.
تحليل تعقيد الوقت
تساعد أشجار العودية في تحليل التعقيد الزمني للخوارزميات العودية. من خلال فحص بنية الشجرة، يمكننا تحديد عدد الاستدعاءات العودية التي تم إجراؤها والعمل المنجز على كل مستوى. يساعد هذا التحليل في فهم الكفاءة الإجمالية للخوارزمية وتحديد أي أوجه قصور محتملة أو فرص للتحسين.
مقدمة
- فكر في برنامج يحدد مضروب الرقم. تأخذ هذه الدالة الرقم N كمدخل وترجع مضروب N نتيجة لذلك. سوف يشبه الكود الزائف لهذه الوظيفة،
// find factorial of a number factorial(n) { // Base case if n is less than 2: // Factorial of 0, 1 is 1 return n // Recursive step return n * factorial(n-1); // Factorial of 5 => 5 * Factorial(4)... } /* How function calls are made, Factorial(5) [ 120 ] | 5 * Factorial(4) ==> 120 | 4. * Factorial(3) ==> 24 | 3 * Factorial(2) ==> 6 | 2 * Factorial(1) ==> 2 | 1 */ - يتم تمثيل العودية بالوظيفة التي تم ذكرها مسبقًا. نحن نقوم باستدعاء دالة لتحديد مضروب الرقم. ثم، بالنظر إلى قيمة أقل لنفس الرقم، تستدعي هذه الوظيفة نفسها. يستمر هذا حتى نصل إلى الحالة الأساسية، والتي لا يوجد فيها المزيد من استدعاءات الوظائف.
- العودية هي تقنية للتعامل مع المشكلات المعقدة عندما تعتمد النتيجة على نتائج مثيلات أصغر لنفس المشكلة.
- إذا فكرنا في الدوال، يقال إن الدالة متكررة إذا استمرت في استدعاء نفسها حتى تصل إلى الحالة الأساسية.
- تحتوي أي دالة عودية على مكونين أساسيين: الحالة الأساسية والخطوة العودية. نتوقف عن الذهاب إلى المرحلة العودية بمجرد وصولنا إلى الحالة الأساسية. لمنع التكرار الذي لا نهاية له، يجب أن تكون الحالات الأساسية محددة بشكل صحيح وهي حاسمة. تعريف العودية اللانهائية هو العودية التي لا تصل أبدًا إلى الحالة الأساسية. إذا لم يصل البرنامج مطلقًا إلى الحالة الأساسية، فسيستمر حدوث تجاوز سعة المكدس.
أنواع العودية
بشكل عام، هناك شكلان مختلفان من التكرار:
- العودية الخطية
- العودية شجرة
- العودية الخطية
العودية الخطية
- يقال إن الوظيفة التي تستدعي نفسها مرة واحدة فقط في كل مرة يتم تنفيذها هي وظيفة متكررة خطيًا. من الأمثلة الجيدة على العودية الخطية هي الدالة مضروبة. يشير اسم 'العودية الخطية' إلى حقيقة أن الدالة العودية الخطية تستغرق وقتًا خطيًا للتنفيذ.
- ألق نظرة على الكود الزائف أدناه:
function doSomething(n) { // base case to stop recursion if nis 0: return // here is some instructions // recursive step doSomething(n-1); } - إذا نظرنا إلى الدالة doSomething(n)، فإنها تقبل معلمة تسمى n وتقوم ببعض العمليات الحسابية قبل استدعاء نفس الإجراء مرة أخرى ولكن بقيم أقل.
- عندما يتم استدعاء الأسلوب doSomething() بقيمة الوسيطة n، فلنفترض أن T(n) يمثل إجمالي مقدار الوقت اللازم لإكمال الحساب. لهذا، يمكننا أيضًا صياغة علاقة تكرارية، T(n) = T(n-1) + K. K بمثابة ثابت هنا. يتم تضمين الثابت K لأنه يستغرق وقتًا حتى تقوم الوظيفة بتخصيص أو إلغاء تخصيص الذاكرة لمتغير أو إجراء عملية حسابية. نستخدم K لتحديد الوقت لأنه دقيق جدًا وغير مهم.
- يمكن حساب التعقيد الزمني لهذا البرنامج العودي ببساطة، لأنه في أسوأ السيناريوهات، تسمى الطريقة doSomething() n مرات. بشكل رسمي، التعقيد الزمني للدالة هو O(N).
العودية شجرة
- عندما تقوم بإجراء استدعاء عودي في حالتك التكرارية أكثر من مرة، يُشار إلى ذلك باسم التكرار الشجري. أحد الأمثلة الفعالة على عودية الشجرة هو تسلسل فيبوناتشي. تعمل الدالات العودية للشجرة في زمن أسي؛ فهي ليست خطية في تعقيدها الزمني.
- ألق نظرة على الكود الزائف أدناه،
function doSomething(n) { // base case to stop recursion if n is less than 2: return n; // here is some instructions // recursive step return doSomething(n-1) + doSomething(n-2); } - والفرق الوحيد بين هذا الرمز والرمز السابق هو أن هذا الكود يقوم بإجراء مكالمة أخرى لنفس الوظيفة بقيمة n أقل.
- لنضع T(n) = T(n-1) + T(n-2) + k كعلاقة تكرارية لهذه الوظيفة. K بمثابة ثابت مرة أخرى.
- عند إجراء أكثر من استدعاء لنفس الوظيفة بقيم أصغر، يُعرف هذا النوع من التكرار باسم التكرار الشجري. والجانب المثير للاهتمام الآن هو: ما مدى استهلاك هذه الوظيفة للوقت؟
- قم بالتخمين بناءً على شجرة العودية أدناه لنفس الوظيفة.
- قد يتبادر إلى ذهنك أنه من الصعب تقدير التعقيد الزمني من خلال النظر مباشرة إلى دالة عودية، خاصة عندما تكون شجرة عودية. تعد طريقة شجرة العودية إحدى التقنيات العديدة لحساب التعقيد الزمني لهذه الوظائف. دعونا نفحصها بمزيد من التفصيل.
ما هي طريقة شجرة العودية؟
- يتم حل علاقات التكرار مثل T(N) = T(N/2) + N أو العلاقتين اللتين تناولناهما سابقًا في قسم أنواع التكرار باستخدام نهج شجرة التكرار. غالبًا ما تستخدم هذه العلاقات المتكررة استراتيجية فرق تسد لمعالجة المشكلات.
- يستغرق الأمر وقتًا لدمج الإجابات على المشكلات الفرعية الأصغر التي يتم إنشاؤها عندما يتم تقسيم مشكلة أكبر إلى مشكلات فرعية أصغر.
- علاقة التكرار، على سبيل المثال، هي T(N) = 2 * T(N/2) + O(N) لفرز الدمج. الوقت اللازم للجمع بين إجابات مشكلتين فرعيتين بحجم مشترك T(N/2) هو O(N)، وهو ما ينطبق أيضًا على مستوى التنفيذ.
- على سبيل المثال، نظرًا لأن علاقة التكرار للبحث الثنائي هي T(N) = T(N/2) + 1، فإننا نعلم أن كل تكرار للبحث الثنائي يؤدي إلى مساحة بحث مقطوعة إلى النصف. بمجرد تحديد النتيجة، نخرج من الوظيفة. تمت إضافة علاقة التكرار +1 لأن هذه عملية زمنية ثابتة.
- علاقة التكرار T(n) = 2T(n/2) + Kn هي علاقة يجب مراعاتها. تشير Kn إلى مقدار الوقت اللازم للجمع بين الإجابات للمسائل الفرعية ذات البعد n/2.
- دعونا نصور شجرة العودية لعلاقة التكرار المذكورة أعلاه.
يمكننا استخلاص بعض الاستنتاجات من دراسة شجرة العودية أعلاه، بما في ذلك
جافا إذا بيان آخر
1. حجم المشكلة على كل مستوى هو كل ما يهم لتحديد قيمة العقدة. حجم الإصدار هو n عند المستوى 0، n/2 عند المستوى 1، n/2 عند المستوى 2، وهكذا.
2. بشكل عام، نحدد ارتفاع الشجرة بأنه يساوي log (n)، حيث n هو حجم المشكلة، وارتفاع هذه الشجرة العودية يساوي عدد المستويات في الشجرة. وهذا صحيح لأنه، كما أوضحنا للتو، يتم استخدام استراتيجية فرق تسد من خلال علاقات التكرار لحل المشكلات، والانتقال من حجم المشكلة n إلى حجم المشكلة 1 يتطلب ببساطة اتخاذ خطوات السجل (n).
- خذ بعين الاعتبار قيمة N = 16، على سبيل المثال. إذا سمح لنا بتقسيم N على 2 في كل خطوة، فما عدد الخطوات المطلوبة للحصول على N = 1؟ مع الأخذ في الاعتبار أننا نقسم على اثنين في كل خطوة، فإن الإجابة الصحيحة هي 4، وهي قيمة log(16) للأساس 2.
سجل (16) قاعدة 2
سجل (2 ^ 4) قاعدة 2
4 * السجل (2) للأساس 2، حيث أن السجل (أ) للأساس أ = 1
لذا، 4 * سجل (2) الأساس 2 = 4
3. في كل مستوى يعتبر الحد الثاني في التكرار بمثابة الجذر.
على الرغم من أن كلمة 'شجرة' تظهر في اسم هذه الإستراتيجية، إلا أنك لا تحتاج إلى أن تكون خبيرًا في الأشجار لفهمها.
كيفية استخدام شجرة العودية لحل علاقات التكرار؟
تكلفة المشكلة الفرعية في تقنية شجرة العودية هي مقدار الوقت اللازم لحل المشكلة الفرعية. لذلك، إذا لاحظت عبارة 'التكلفة' المرتبطة بشجرة التكرار، فهي تشير ببساطة إلى مقدار الوقت اللازم لحل مشكلة فرعية معينة.
دعونا نفهم كل هذه الخطوات مع بعض الأمثلة.
مثال
النظر في علاقة التكرار،
تي(ن) = 2تي(ن/2) + ك
حل
تظهر علاقة التكرار المحددة الخصائص التالية،
تنقسم مشكلة حجمها n إلى مشكلتين فرعيتين حجم كل منهما n/2. تكلفة الجمع بين الحلول لهذه المشاكل الفرعية هي K.
يتم تقسيم كل مشكلة حجمها n/2 إلى مشكلتين فرعيتين حجم كل منهما n/4 وهكذا.
في المستوى الأخير، سيتم تقليل حجم المشكلة الفرعية إلى 1. وبعبارة أخرى، وصلنا أخيرًا إلى الحالة الأساسية.
دعونا نتبع الخطوات لحل هذه العلاقة التكرارية،
الخطوة 1: ارسم شجرة العودية
الخطوة 2: احسب ارتفاع الشجرة
نظرًا لأننا نعلم أنه عندما نقسم رقمًا بشكل مستمر على 2، يأتي وقت يتم فيه تقليل هذا الرقم إلى 1. كما هو الحال مع حجم المشكلة N، لنفترض أنه بعد قسمة K على 2، تصبح N مساوية لـ 1، مما يعني، ( ن / 2^ك) = 1
هنا n / 2^k هو حجم المشكلة في المستوى الأخير ويساوي دائمًا 1.
الآن يمكننا بسهولة حساب قيمة k من التعبير أعلاه عن طريق أخذ log() إلى كلا الجانبين. وفيما يلي استنتاج أكثر وضوحا،
ن = 2 ^ ك
- سجل (ن) = سجل (2 ^ ك)
- سجل (ن) = ك * سجل (2)
- ك = سجل (ن) / سجل (2)
- ك = سجل (ن) قاعدة 2
إذن ارتفاع الشجرة هو log (n) للقاعدة 2.
الخطوة 3: حساب التكلفة على كل مستوى
- التكلفة عند المستوى 0 = K، تم دمج مشكلتين فرعيتين.
- التكلفة عند المستوى 1 = K + K = 2*K، تم دمج مشكلتين فرعيتين مرتين.
- التكلفة عند المستوى 2 = K + K + K + K = 4*K، يتم دمج مشكلتين فرعيتين أربع مرات. وما إلى ذلك وهلم جرا....
الخطوة 4: حساب عدد العقد في كل مستوى
منشئ سلسلة جافا
دعونا أولاً نحدد عدد العقد في المستوى الأخير. من شجرة التكرار يمكننا أن نستنتج ذلك
- المستوى 0 لديه عقدة واحدة (2^0).
- المستوى 1 يحتوي على عقدتين (2^1).
- المستوى 2 يحتوي على 4 عقد (2^2).
- المستوى 3 يحتوي على 8 (2^3) عقد
لذا يجب أن يحتوي سجل المستوى (n) على عقدتين ^(log(n)) أي عقد n.
الخطوة 5: تلخيص تكلفة جميع المستويات
- يمكن كتابة التكلفة الإجمالية على النحو التالي:
- التكلفة الإجمالية = تكلفة جميع المستويات باستثناء المستوى الأخير + تكلفة المستوى الأخير
- التكلفة الإجمالية = تكلفة المستوى 0 + تكلفة المستوى 1 + تكلفة المستوى 2 +.... + تكلفة سجل المستوى (ن) + تكلفة المستوى الأخير
يتم حساب تكلفة المستوى الأخير بشكل منفصل لأنه الحالة الأساسية ولا يتم إجراء أي دمج على المستوى الأخير، لذا فإن تكلفة حل مشكلة واحدة على هذا المستوى هي قيمة ثابتة. فلنأخذها يا (١).
دعونا نضع القيم في الصيغ،
- T(n) = K + 2*K + 4*K + .... + سجل(n)` مرات + `O(1) * n
- T(n) = K(1 + 2 + 4 + .... + سجل(n) مرات)` + `O(n)
- T(n) = K(2^0 + 2^1 + 2^2 + ....+ سجل(n) مرات + O(n)
إذا ألقيت نظرة عن كثب على التعبير أعلاه، فإنه يشكل تقدمًا هندسيًا (a، ar، ar^2، ar^3 ...... وقت لا نهائي). يتم إعطاء مجموع GP بواسطة S(N) = a / (r - 1). هذا هو الحد الأول و r هي النسبة المشتركة.