تحديات برمجيةحساب الـ Big-O Notation
- تقييم أداء الخوارزميات
- مفهوم المعادلة O(1)
- مفهوم المعادلة O(n)
- مفهوم المعادلة O(log n)
- مفهوم المعادلة O(nk)
- مفهوم المعادلة O(n log n)
- مفهوم المعادلة O(n!)
- مفهوم المعادلة O(kn)
تقييم أداء الخوارزميات
في هذا الدرس ستتعلم كيف تقوم بتقييم أداء الخوارزميات و كيف يتم قراءة التقييم لمعرفة ما إن كان فعال أم لا.
كما أننا سنعلمك كيف تستطيع حساب الوقت الذي يستغرقه الكود حتى يتنفذ بنفسك.
عندما نقوم بتقدير وقت تنفيذ أي خوارزمية (أكثر وقت تحتاجه) فإن النتيجة النهائية ستكون أحد النتائج المذكورة في الجدول التالي.
ما يجب أن تفهمه من الرسم أنه كلما كان الوقت الذي تستغرقه الخوارزمية منخفض كلما كان أداؤها أفضل.
و بالتالي المعادلة O(1) تعتبر الأفضل بينهم و المعادلة O(n!) تعتبر الأسوء على الإطلاق.
عند تقدير وقت الخوارزمية, يجب مقارنة أداءها على أساس الرسم السابق.
فمثلاً إذا وجدنا أداء الكود هو O(n!) فسنحاول إيجاد حل آخر يتنفذ بوقت أقل.
المعادلات التي تشير لتقييم جيد:
- O(1)
- O(log n)
- O(n)
- O(n log n)
المعادلات التي تشير لتقييم سيء:
- O(nk)
- O(kn)
- O(n!)
في الصورة التالية وضعنا ترتيب جميع المعادلات من الأفضل إلى الأسوأ بشكل أسهل لك في الحفظ.
مفهوم المعادلة O(1)
من المهم جداً معرفة أن الرقم 1 في هذه المعادلة لا يشير للقيمة واحد, بل يعني أن كل أمر موضوع في الكود سيتنفذ مرة واحدة فقط.
بمعنى آخر, هذه المعادلة تعني أن الكود لا يحتوي على حلقات ( Loops ) و لا على دوال تستدعي نفسها ( Loops ).
إذا كان تقييم الكود هو O(1) فهذا يعني أنه ممتاز و يتنفذ بسرعة عالية جداً و لا يحتاج لأي تحسين.
و هو يعني أيضاً أن الوقت المتوقع لتنفيذ الكود ثابت ( Constant Time ) لا يتغير.
مثال
طريقة تقييم أداء الكود
Execution Steps = 1 + 1 + 1 + 1 = 4 Big O of any constant ==> O(1)
بما أن جميع الأوامر الموضوعة تتنفذ مرة واحدة فتقييم هذا الكود هو O(1).
كما تلاحظ فإننا لا نهتم بعدد الخطوات المعروفة عند وضع التقييم النهائي بل نهتم بكم مرة ستكرر هذه الخطوات و في حال كانت لا تتكرر فإنها لا تدخل في التقييم.
مفهوم المعادلة O(n)
المتغير n
في هذه المعادلة يعني أن الكود سيتنفذ بعدد قيمة n
كما هي الحال عندما نضع الكود بداخل حلقة.
بمعنى آخر, هذه المعادلة تعني أنه كلما كانت قيمة n
أكبر, كلما كان الوقت الذي سيستغرقه تنفيذ الكود أكبر.
بما أن الوقت الذي تستغرقه هذه المعادلة يكبر بشكل متوازن مع كبر حجم الأوامر فهنا رسم التقييم سيكون خط مائل متوازن بينهما يسمى ( Linear Time ).
إذا كان تقييم الكود هو O(n) فهذا يعني أنه جيد و مقبول.
ملاحظة: إذا كان تقييم الكود جيد و لكن يمكن كتابته بطريقة أخرى أكثر بساطة و لا تتطلب استخدام حلقة, فالأولى أن نقوم بالتخلي عن الحلقة و اعتماد تلك الطريقة.
المثال الأول
طريقة تقييم أداء الكود
Execution Steps = 1 + n + 1 Execution Steps = 2 + n Big O of 2 + n ==> O(n)
كما سبق و قلنا, الخطوات العادية أو الأوامر التي تتنفذ مرة واحدة لا تعتبر مهمة في تقييم أداء الكود.
عند تقييم الكود هنا لاحظ أننا لم نهتم إطلاقاً بعدد الخطوات الثابتة التي ستتنفذ, أي لم نهتم بالرقم 2
الذي يظهر في الـ Step Execution و لكننا إهتممنا فقط بالمتغير n
الموضوع فيها.
عند تقييم أداء الكود فإننا دائماً ننظر لأعلى قيمة مجهولة ممكنة و في حالتنا هنا يعتبر المتغير n
هو الأعلى لذلك كان التقييم النهائي لهذا الكود هو O(n).
إذا كانت قيمة n
مقسومة على رقم مثل n / 2
هل ستتغير المعادلة؟
كلا لن تتغير, لأن قيمة n
لا تزال مجهولة سواء كانت مقسومة أم لا و هذا ما سنراه في المثال التالي.
المثال الثاني
طريقة تقييم أداء الكود
Execution Steps = 1 + (n/2) + 1 Execution Steps = 2 + (n/2) Big O of 2 + (n/2) ==> O(n)
إذاً, سواء كانت الحلقة تتوقف عند n
أو تتوقف عند n / 2
فتقييم الكود سيبقى كما هو.
ماذا ستكون المعادلة لو كانت الحلقة تسير بشكل عكسي؟
لا يؤثر هذا الأمر إطلاقاً على المعادلة, فمثلاً إذا كنت ستذهب من النقطة A
إلى النقطة B
أو بالعكس من B
إلى النقطة A
فعدد الخطوات للوصول هنا نفسه تماماً.
بنفس المنطق إذا أنشأنا حلقة تسير من 1
إلى n
أو أنشأنا حلقة تسير من n
إلى 1
فعدد المرات التي سيتنفذ فيها الكود هو نفسه تماماَ.
لذلك المعادلة O(n) تظل نفسها في كلا الحالتين و هذا ما سنراه في المثال التالي.
المثال الثالث
طريقة تقييم أداء الكود
Execution Steps = 1 + n + 1 Execution Steps = 2 + n Big O of 2 + n ==> O(n)
ماذا لو كانت الحلقة تتنفذ عدد مرات محدد, هل ستتغير المعادلة؟
طبعاً لأن شرط المعادلة الأساسي لتكون O(n) هو أن يكون عدد المرات التي سيتنفذ فيها الكود مجهولاً.
إذا كان عدد المرات الذي ستكرر فيه الحلقة معروفاً, فإن تقييم الخوارزمية سيكون O(1) لأنه عدد المرات التي سيتنفذ فيها الكود ثابت لا يتغير و هذا ما سنراه في المثال التالي.
المثال الرابع
طريقة تقييم أداء الكود
Execution Steps = 1 + 5 + 1 Execution Steps = 7 Big O of any constant ==> O(1)
مفهوم المعادلة O(log n)
المقصود بالمعادلة log n
هو عندما تتغير قيمة عداد الحلقة بشكل مضاعف أو مقسوم.
المثال الأول
في المثال التالي قمنا بجعل عدّاد الحلقة يتم ضربه بإثنين في كل دورة.
طريقة تقييم أداء الكود
Execution Steps = 1 + log n + 1 Execution Steps = 2 + log n Big O of 2 + log n ==> O(log n)
المثال الثاني
في المثال التالي قمنا بجعل عدّاد الحلقة يتم قسمته على اثنين في كل دورة.
طريقة تقييم أداء الكود
Execution Steps = 1 + log n + 1 Execution Steps = 2 + log n Big O of 2 + log n ==> O(log n)
مفهوم المعادلة O(nk)
المقصود بالحرف n
هو أن الكود موضوع بداخل حلقة.
المقصود بالحرف k
أن الحلقة تحتوي أيضاً على حلقة أو أكثر بشكل متداخل ( Nested Loop ).
عند وضع التقييم للكود, الحرف n
نضعه كما هو ليشير أنه يوجد حلقة, أما الحرف k
فنضع مكانه عدد الحلقات المتداخلة و إليك بعض الأمثلة:
- إذا كان الكود يتضمن حلقتين متداخلتين نكتب O(n2)
- إذا كان الكود يتضمن ثلاث حلقات متداخلة نكتب O(n3)
- إذا كان الكود يتضمن أربع حلقات متداخلة نكتب O(n4) و هكذا.
لا تقلق ستتضح لك الفكرة من الأمثلة.
المثال الأول
في المثال التالي قمنا بوضع حلقة بداخل حلقة.
طريقة تقييم أداء الكود
Execution Steps = 1 + n * n + 1 Execution Steps = 2 + n^2 Big O of 2 + n^2 ==> O(n^2)
المثال الثاني
في المثال التالي قمنا بوضع ثلاث حلقات متداخلة.
طريقة تقييم أداء الكود
Execution Steps = 1 + n * n * n + 1 Execution Steps = 2 + n^3 Big O of 2 + n^3 ==> O(n^3)
مفهوم المعادلة O(n log n)
المقصود بهذه المعادلة أنه يوجد حلقتين متداخلتين. الحلقة الخارجية تتنفذ بمقدار n
تماماً كالمعادلة O(n). و الحلقة الداخلية تتنفذ نسبة لقيمة n
أيضاً و لكن العداد الخاص بها تتغير قيمته بشكل مضاعف أو مقسوم تماماً كالمعادلة O(log n).
مثال
طريقة تقييم أداء الكود
Execution Steps = 1 + n * log n + 1 Execution Steps = 2 + n * log n Big O of 2 + n log n ==> O(n log n)
مفهوم المعادلة O(n!)
المقصود بهذه المعادلة أن الدالة ستعيد إستدعاء نفسها بمقدار قيمة n
.
ملاحظة: الكود الموضوع في المثال التالي تم شرحه بتفصيل ممل في دورة الخوارزميات و بالتحديد في درس تعريف دوال تستدعي نفسها
مثال
طريقة تقييم أداء الكود
Execution Steps = n! + 1 Big O of n! + 1 ==> O(n!)
مفهوم المعادلة O(kn)
المقصود بهذه المعادلة أن الدالة ستعيد إستدعاء نفسها بمقدار قيمة n
و في كل عملية إستدعاء سيتم استدعاءها بشكل مضاعف أيضاً.
فعلى سبيل المثال, أول مرة تستدعي فيها نفسها, تقوم باستدعاء نفسها مرتين بشكل متوازي.
ثاني مرة تستدعي فيها نفسها, تقوم باستدعاء نفسها 4 مرات بشكل متوازي.
ثالث مرة تستدعي فيها نفسها, تقوم باستدعاء نفسها 8 مرات بشكل متوازي.
رابع مرة تستدعي فيها نفسها, تقوم باستدعاء نفسها 16 مرة بشكل متوازي و هكذا.
مثال
في المثال التالي سنقوم بتطبيق مبدأ يسمى فايبوناتشي ( Fibonacci ).
بكل صراحة فكرة هذا المبدأ تعتبر بسيطة جداً و لكن تطبيقه بهذا الأسلوب سيكون غريب بالنسبة لك و لقد تعمدنا كتابته بهذه الشكل حتى نستخدم المعادلة O(kn)
بشكل عام فكرة الكود أنك في كل مرة ستجمع القيمة ما قبل الأخيرة مع القيمة الأخيرة و تضع الناتج بعدهما كما في الصورة التالية.
طريقة تقييم أداء الكود
Execution Steps = 2^n Big O of 2^n ==> O(k^n)
الفيديو التالي يشرح طريقة عمل الدالة عند استدعائها و كيف أنها تستدعي نفسها أكثر من مرة في كل عملية إستدعاء.
في الدرس التالي سنضع تمارين يمكن حلها بأكثر من طريقة و لكننا سنعرف أي طريقة هي الأفضل بناءً على تقييم الكود الذي تعلمنا كيف نحسبه في هذا الدرس.