|
السلام عليكم
متل ما منعرف أنو الغاية من هالموضوع كله هي تحديد الخوارزمية الأكثر فعالية.
لنفرض أنه من أجل مسألة مطروحة لدينا ثلاثة خوارزميات تعقيدها:
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 ولكنهما لا يعطيان توصيفاً لفعالية الخوارزمية لأنهما لا يعبران عن أسوأ الأحوال.
ان شاء الله يكون فيه فائدة للكل ..
|
أرسل من قبل 
