الخوارزميات التداخلية (Recursive algorithms)

الخوارزميات التداخلية (Recursive algorithms)

الخوارزميات التداخلية هي الخارزميات التي تستدعي نفسها حيث ان الطريقة الافضل لتحليل تعقيدات وقتها هو بكتابة علاقات تداخل (Recurrence relations) تمثل تعقيدات الوقت لها، ثم بعد ذلك القيام بحل هذه العلاقات للحصول على تعقيدات الوقت.
مثال5/ عودة للمسألة في المثال رقم 1.

تستخدم الخوارزمية التالية لحل هذه المسألة باستخدام اسلوب التداخل:

Algorithm Rsum(A,n):
Input: a positive integer n and an array A indexed
from 1 to n.
Output:S , the sum of the numbers in A.
1. if n ? 0 then
2. S 0
3. else
4. S Rsum(A,n-1)+ A[n]
5. end if
6. return S

يتصف مثال المسألة بـ n

تعقيدات الخزن: كل استدعاء يحتاج خليتان واحدة للمتغير S واخرى لعنوان العودة (return address) وبما ان عدد الاستدعاءات يحسب بالعلاقة التالية:


عمق التداخل= الحجم الاولي في اول تنشيط – الحجم النهائي في اخر تنشيط +1

= n - 0 +1

= n + 1

اذن تعقيدات الخزن هي

SRsum(n)= 2(n+1)

تعقيدات الوقت باستخدام اسلوب عد الخطوات: يصاغ الوقت على شكل علاقة تداخل ثم تستخدم طريقة التعويض التكراري (Iterative substitution) لحلها.






TRsum(n)= 3 + TRsum(n-1)
= 3 + [3 + TRsum(n-2)]
= 2(3) + TRsum(n-2)
= 2(3) + [3 + TRsum(n-3)]
= 3(3) + TRsum(n-3)
.
.
.
= m(3) + TRsum(n-m)
عندما n=m يكون لدينا
TRsum(n)= 3n + 3

الحالات الافضل والاسوأ والمتوسطة ( Best & worst & Average cases)

يمكن التخلص من الصعوبات في الحالات التي تكون فيها المعاملات المختارة( خصائص المثال) غير مناسبة وحدها لتحديد عدد الخطوات من خلال تعريف ثلاث انواع من عد الخطوات:-
1) عد خطوات الحالة الافضل:- وهو ادنى عدد من الخطوات يمكن انجازها لمعاملات معينة.
2) عد خطوات الحالة الاسوأ:- وهو اقصى عدد من الخطوات يمكن انجازها لمعاملات معينة.
3) عد خطوات الحالة المتوسطة:- وهوالعدد المتوسط من الخطوات التي يمكنانجازها على امثلة مسألة بمعاملات معينة.

مثال6/ ايجاد العنصرالاكبر.
Algorithm arrayMax(A,n):
Input: An array A storing n integers.
Output: currentMax,the maximum element in A.
1. currentMax A[1]
2. for i 2 to n
3. if currentMax < A[i] then
4. currentMax A[i]
5. end if
6. end for
7. return currentMax

يتصف مثال المسألة بـ n

تعقيدات الوقت باستخدام اسلوب عد الخطوات:

الحالة الافضل : تحدث عندما A[1] هو العنصر الاكبر

الحالة الاسوأ : تحدث عندما تكون A مرتبة تصاعديا


الحالة المتوسطة: تحسب متوسط التعقيدات لجميع الحالات الممكنة لقيم المصفوفة