الصيغ التقاربية ( Asymptotic notations)

الصيغ التقاربية ( Asymptotic notations)

برهنت عملية تحديد عد الخطوات لخوارزمية ما على انها مهمة عالية الصعوبة ولذلك اصطلح على استعمال تدوينات تقاربية ذات معنى لتعقيدات الخوارزمية.

1) صيغة الحد الاعلى ( Big-Oh)

تعريف:- f(n)=O(g(n)) اذا وفقط اذا وجد ثابتان موجبان(c > 0) c و (n0 ? 0) n0
بحيث يكون f(n) ? c g(n) لجميع قيم n ? n0 .
يقول التعريف ان الدالة f على الأكثر تنمو بسرعة ثابت معين c مضروب في الدالة g.
نظرية/ اذا كانت f(n)= am nm + am-1 nm-1 +…+ a1 n + a0 متعددة حدود درجتها m
فانf(n)= O(nm) .

مثال/ 3n+2= O(n)
لأن 3n+2 ? 4n لجميع قيم n ? 2
مثال/ 100=O(1)
لأن 100 ? 100*1 لجميع قيم n ? 0
مثال/ 10n2 + 4n + 2=O(n2)
لأن 10n2 + 4n + 2 ? 11n2 لجميع قيم n ? 5
مثال/ 6*2n + n2= O(2n)
لأن 6*2n + n2 ? 7*2n لجميع قيم n ? 4
مثال/ 3n+2 ? O(1) و 10n2 + 4n + 2 ? O(n)

2) صيغة الحد الادنى ( Big-Omega)

تعريف:- f(n)= ? (g(n)) اذا وفقط اذا وجد ثابتان موجبان(c > 0) c و (n0 ? 0) n0
بحيث يكون f(n) ? c g(n) لجميع قيم n ? n0 .
يقول التعريف ان الدالة f على الاقل تنمو بسرعة ثابت معين c مضروب في الدالة g،
وكما واضح من التعريف فان f(n)= ?(g(n)) اذا وفقط اذا g(n)=O(f(n)).

نظرية/ اذا كانت f(n)= am nm + am-1 nm-1 +…+ a1 n + a0 متعددة حدود درجتها m
فان f(n)= ? (nm) .
مثال/ 3n+2= ? (n)
لأن 3n+2 ? 3n لجميع قيم n ? 0
مثال/ 100= ? (1)
لأن 100 ? 100*1 لجميع قيم n ? 0
مثال/ 10n2 + 4n + 2= ? (n2)
لأن 10n2 + 4n + 2 ? 10n2 لجميع قيم n ? 0
مثال/ 6*2n + n2= ? (2n)
لأن 6*2n + n2 ? 6*2n لجميع قيم n ? 0
مثال/ 3n+2 ? ? (n2) و 10n2 + 4n + 2 ? ? (n3)




3) صيغة الحد الأعلى- الادنى ( Big-Theta)

تعريف:- f(n) = ?(g(n)) اذا وفقط اذا وجدت ثوابت موجبة n0 و c1 و c2 بحيث
يكون c1 g(n) ? f(n) ?c2 g(n) لجميع قيم n ? n0 .

نظرية/ اذا كانت f(n)= am nm + am-1 nm-1 +…+ a1 n + a0 متعددة حدود درجتها m
فانf(n)= ? (nm)
مثال/ 3n+2= ? (n)
لأن 3n ? 3n+2 ? 4n لجميع قيم n ? 2
مثال/ 100= ? (1)
لأن 100*1 ? 100 ? 100*1 لجميع قيم n ? 0
مثال/ 10n2 + 4n + 2= ? (n2)
لأن 10n2 ?10n2 + 4n + 2 ? 11n2 لجميع قيم n ? 5

مثال/ 3n+2 ? ? (n2) و 3n+2 ? ? (1)

ملاحظة/ هذه الصيغة هي الأكثر دقة وتتحقق اذا كان g(n) هو الحد الأدنى والأعلى للدالة f(n).



مسألة/ برهن ان العلاقات التالية صحيحة
1) 5n2 – 6n = ? (n2)
2) 38n3 + 4n2 = ? (n3)

الصيغ الشائعة لتعقيدات الوقت والخزن
هذه بعض الصيغ الشائعة الاستخدام في التعقيدات
O(1) < O(log n) < O(n) < O(n log n)
الخوارزميات التي لها تعقيدات اكبر من O(n log n) تعد غير عملية والخوارزميات التي لها تعقيدات اسية2n) O( مخيفة ولا تكون عملية الا عندما تكون n صغيرة جدا( اقل من 40).

توضيح/ بافتراض حاسوب ينفذ 109 ايعاز بالثانية وعندما تكون f(n)=2n فان:

n= 10 20 30 40 50 100 1000
f(n)= 1?s 1ms 1sec 18.3min 13day 4*1013 year 32*10238 year





مثال7/ عودة لبعض المسائل السابقة واعادة تحليلها بالصيغ التقاربية.
1- الخوارزمية sum
1. ……… ?(1)
2. ……… ?(n)
3. ……… ?(n)
5. ……… ?(1)



2- الخوارزمية add
1. ……… ?(m)
2. ……… ?(n)
3. ……… ?(mn)
6. ……… ?(mn)



3- الخوارزمية fibonacci

1. ………. ?(1)
2. ………. ?(1)
4. ………. ?(1)
5. . ……... ?(1)
6. ………. ?(n)
7. ………. ?(n)
8. . .…….. ?(n)
9. ………. ?(n)
12. ……… ?(1)