ماهو تعقيد هذه الخوارزمية

على ما اذكر هذا الموضوع ..

والصراحة اريد ان ارجعه جيدا ..

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

- جملة رياضية او تعبير رياضي ..EX

- جملة شرطية او احتمال If - Case ,,,,

- دوارة او حلقة For - While ..

...

0 - عملية المساواة الاولى على حسب ما اذكر تأخذ قيمة لانها عملية اسناد لذلك فانها تأخذ وحدة زمنية واحدة (1) .

1- الحلقة تأخذ زمن بقدر عدد الحلقات .. لذلك فان التعقيد اولا يكون n ... لان عدد الحلقات n .. ولكل حلقة تأخذ وحدة زمن واحد .

اذن :- n *1 = n

ولكن بما انه لديك عملية اختبار لشرط التوقف .. فهنا لديك شرط ينفذ لكن لا يحقق وهو شرط التوقف .. وهي الحالة التي تساوي بها الn =0

لذلك زمن الحلقة الكلي هو n +1 ... عدد الحلقات + شرط التوقف الغير متحقق ...

2- بعدها الشرط مع العملية الحسابية تأخذ وحده واحدة (1)

3 - التعبير الرياضي يأخذ وحدة واحدة .

4- تعبير رياضي اخر يأخذ 1 ايضا ..

5- تعبير اخر يأخذ 1 ..

النتيجة ستكون بجمع هذه القيم ..

1 + n + 1 + 1 + 1 +1    = n +5

,,,,

اذن التعقيد الزمني لهذه الدالة هو من النوع N اي ان الدالة ستنفذ بعدد مرات الحلقة مجموع معها محتويات تلك الحلقة ..

هذا ما اذكره ممكن يصححون لنا الاخوان لو اخطئت في شئ .. لكن اتمنى ان تكون صحيحه لانني اريد ان اتذكرها جيدا ..

تحياتي العطرة ..

سيف سوف كتب:

السلام عليكم ورحمة الله وبركاته

أريد شرح لكيفية إيجاد تعقيد هذه الخوارزمية

factor = x;
while (n>0)
{
    if((n mod 2) == 1)
       res = res * factor;
    factor = factor * factor;
 n = n div 2;
}

:sad: :sad: :sad:

In [1]: def f(n):
   ...:     count=0
   ...:     while n>0:
   ...:         count+=1
   ...:         n=n/2
   ...:     return count
   ...: 

In [2]: f(100)
Out[2]: 7

In [3]: f(10000)
Out[3]: 14

In [4]: f(1000000)
Out[4]: 20

خلني اجرب حظي ,

اتوقع O(N/2)

عزيزي ببساطة تحاول تلخيص الخوارزمية إلى الجزء المؤثر. بمعنى لو نظرنا إلى الخوارزمية التي تطرحها فالجزء المؤثر هو الحلقة. هذه الحلقة تعتمد على متغير واحد هو n. و عملية الوصول إلى شرط الخروج من الحلقة أو سمها ما شئت reduction أو دون تسمية هو وصول المتغير إلى القيمة صفر. و هناك عبارة داخل الحلقة تقوم بعملية الـ reduction و هي القسمة على اثنين. بالتالي, فإنك يمكن أن تنظر إلى الأمر على أنه عدد يقسم على اثنين في كل مرة, بالتالي فإن تعقيد الخوارزمية log n. مثلاً لو كانت n عبارة عن 128 فإننا نحتاج إلى ثمان عمليات قسمة على اثنين للوصول إلى الصفر.

بارك الله فيكم على الاجابة

هل هناك كتاب بالعربي على تعقيدات الخوارزميات

:happy: :happy: