CSC - SY

السلام عليكم

متل ما منعرف أنو الغاية من هالموضوع كله هي تحديد الخوارزمية الأكثر فعالية.

لنفرض أنه من أجل مسألة مطروحة لدينا ثلاثة خوارزميات تعقيدها:
f(n) = 3n + 6
g(n) = 6n
h(n) = 4n^2

أنظر إلى كل من g وتعريف Big O:
من أجل c = 6 و n0 = 1 (إن صفر – في حال لم تظهر واضحة) يكون
g(n) <= c.n
أي يمكن أن نقول أن

كود:
g(n) = O (n)
تذكر أن Big O تستخدم في أسوأ الأحوال. تقرأ السطر السابق: g هي Big O ل n.
لاحظ هنا ظهور مفهوم التعقيد المقارب حيث أهمل الثابت الضربي 6 حيث نقول أن التابع g يتزايد بأسوأ الأحوال مثل n. تعقيد خطي.
بدراسة مماثلة ل h نجد أن h تتزايد بأسوأ الأحوال مثل n^2. تعقيد من الدرجة الثانية:
كود:
h(n) = O(n^2)
أما f(n) مستماثل g من حيث Big O.

إذاً: بما أن f و g تأخذ O(n) بينما h تأخذ O(n^2) فكلاهما أكثر فعالية من h.

ويتم اختيار أحدهما. إذاً لا حاجة لمعرفة تابع التعقيد إذا تمكنا من معرفة أوه الكبيرة لخوارزمية ما ( سنعرف فيما بعد كيف يمكننا نعرفتها دون إيجاد تابع التعقيد).

ملاحظة أخيرة: من الواضح أن g أسوأ من f ولكن هذا الفرق الصغير يهمل أمام الفرق الذي سينتج عن استخدام h. فمن أجل n = 1000000 يكون:
f(n) = 3000006
g(n) = 6000000
h(n) = 4000000000000
ولذلك نحن نستخدم التعقيد المقارب لأنه لا فرق كبير بين g و f. نقول عنهما أنهما من نفس الدرجة (O(n)). (أرجو أن تكون الفكرة قد وصلت).

المزيد من الأمثلة التوضيحية:
كود:
7n^2 + 2n + 1 =O(n^2) = O(n^3)
طبعاً هذا الكلام صحيح، لكنه يبعدنا عن التمثيل الصحيح لفعالية الخوارزمية لذلك نبحث لكل خوارزمية عن أفضل Big O ممكنة. نلغي O(n^3).

هذا مثال مهم:
كود:
f(n) = 4 = O (1)
إن أفضل الخوارزميات هي الخوارزميات التي تنفذ عدداً ثابتاً من العمليات مهما كان حجم المعطيات n. سنذكر مثالاً عليها عند دراسة Fibonacci.

لاحظ أن تطبيق الصيغتين الأخريتين مشابه لتطبيق Big O ولكنهما لا يعطيان توصيفاً لفعالية الخوارزمية لأنهما لا يعبران عن أسوأ الأحوال.

ان شاء الله يكون فيه فائدة للكل ..

ممكن حدا يقول لي كيف يتم حساب تعقيد الخوارزمية في حال كان لدينا حلقات for&&if كالمثال التالي:
for i:=1 to n do
if(i mod3)then
forj=1 to n do
x=x+3

esle
for j=1 to i do
y=y*2

على حد علمي:
رح ينفذ الـ X=X+3 بس لما تكون i من مضاعفات الـ 3
يعني رح يدخل عالـ if بمقدار 1\3 عدد المرات ..... يعني:
1\3 (سيغما(i من ال 1 إلى الـ n)*سيغما(j من الـ 1 إلى الـ n)

+

2\3 (سيغما(i من ال 1 إلى الـ n)*سيغما(j من الـ 1 إلى الـ i)

طيب إذا كان عنا حلقة while بدل for بس
داخل الحلقة يوجد اختبار if
إذا تحقق الشرط يزداد العداد بمقدار 2
وإلا يزداد بمقدار 3
شو الحل ياعالم

شو في حل ولا لاء
wating.....

اكتب الكود كامل لحتى احسن ساعدك ......