تحديات برمجيةحساب الـ Big-O Notation

تقييم أداء الخوارزميات
مفهوم المعادلة O(1)
مفهوم المعادلة O(n)
مفهوم المعادلة O(log n)
مفهوم المعادلة O(n^k)
مفهوم المعادلة O(n log n)
مفهوم المعادلة O(n!)
مفهوم المعادلة O(kⁿ)

تقييم أداء الخوارزميات

في هذا الدرس ستتعلم كيف تقوم بتقييم أداء الخوارزميات و كيف يتم قراءة التقييم لمعرفة ما إن كان فعال أم لا.
كما أننا سنعلمك كيف تستطيع حساب الوقت الذي يستغرقه الكود حتى يتنفذ بنفسك.

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

ما يجب أن تفهمه من الرسم أنه كلما كان الوقت الذي تستغرقه الخوارزمية منخفض كلما كان أداؤها أفضل.
و بالتالي المعادلة O(1) تعتبر الأفضل بينهم و المعادلة O(n!) تعتبر الأسوء على الإطلاق.

عند تقدير وقت الخوارزمية, يجب مقارنة أداءها على أساس الرسم السابق.
فمثلاً إذا وجدنا أداء الكود هو O(n!) فسنحاول إيجاد حل آخر يتنفذ بوقت أقل.

المعادلات التي تشير لتقييم جيد:

O(1)
O(log n)
O(n)
O(n log n)

المعادلات التي تشير لتقييم سيء:

O(n^k)
O(kⁿ)
O(n!)

في الصورة التالية وضعنا ترتيب جميع المعادلات من الأفضل إلى الأسوأ بشكل أسهل لك في الحفظ.

مفهوم المعادلة O(1)

من المهم جداً معرفة أن الرقم 1 في هذه المعادلة لا يشير للقيمة واحد, بل يعني أن كل أمر موضوع في الكود سيتنفذ مرة واحدة فقط.
بمعنى آخر, هذه المعادلة تعني أن الكود لا يحتوي على حلقات ( Loops ) و لا على دوال تستدعي نفسها ( Loops ).

إذا كان تقييم الكود هو O(1) فهذا يعني أنه ممتاز و يتنفذ بسرعة عالية جداً و لا يحتاج لأي تحسين.
و هو يعني أيضاً أن الوقت المتوقع لتنفيذ الكود ثابت ( Constant Time ) لا يتغير.

مثال

Python
Java
C#
C++
C
def func():     # تعريف الدالة لا يحسب كخطوة

    a = 10      # إسناد القيمة يحسب خطوة
    b = 20      # إسناد القيمة يحسب خطوة
    s = a + b   # إسناد القيمة يحسب خطوة
    
    return s    # إرجاع القيمة يحسب خطوة
    
    # Big-O مجموع الأوامر التي ستتنفذ هو 4 و لكن بما أنها مجرد أوامر عادية لا تتكرر أكثر من مرة فإنها لا تحسب إطلاقاً في معادلة الـ
public int func()   // تعريف الدالة لا يحسب كخطوة
{
    int a, b, s;    // تعريف المتغيرات لا يحسب إطلاقاً
    
    a = 10;         // إسناد القيمة يحسب خطوة
    b = 20;         // إسناد القيمة يحسب خطوة
    s = a + b;      // إسناد القيمة يحسب خطوة
    
    return s;       // إرجاع القيمة يحسب خطوة
    
    // Big-O مجموع الأوامر التي ستتنفذ هو 4 و لكن بما أنها مجرد أوامر عادية لا تتكرر أكثر من مرة فإنها لا تحسب إطلاقاً في معادلة الـ
}
public int Func()   // تعريف الدالة لا يحسب كخطوة
{
    int a, b, s;    // تعريف المتغيرات لا يحسب إطلاقاً

    a = 10;         // إسناد القيمة يحسب خطوة
    b = 20;         // إسناد القيمة يحسب خطوة
    s = a + b;      // إسناد القيمة يحسب خطوة

    return s;       // إرجاع القيمة يحسب خطوة

    // Big-O مجموع الأوامر التي ستتنفذ هو 4 و لكن بما أنها مجرد أوامر عادية لا تتكرر أكثر من مرة فإنها لا تحسب إطلاقاً في معادلة الـ
}
int func() {       // تعريف الدالة لا يحسب كخطوة
    
    int a, b, s;   // تعريف المتغيرات لا يحسب إطلاقاً

    a = 10;        // إسناد القيمة يحسب خطوة
    b = 20;        // إسناد القيمة يحسب خطوة
    s = a + b;     // إسناد القيمة يحسب خطوة
    
    return s;      // إرجاع القيمة يحسب خطوة

    // Big-O مجموع الأوامر التي ستتنفذ هو 4 و لكن بما أنها مجرد أوامر عادية لا تتكرر أكثر من مرة فإنها لا تحسب إطلاقاً في معادلة الـ

}
int func() {       // تعريف الدالة لا يحسب كخطوة
    
    int a, b, s;   // تعريف المتغيرات لا يحسب إطلاقاً

    a = 10;        // إسناد القيمة يحسب خطوة
    b = 20;        // إسناد القيمة يحسب خطوة
    s = a + b;     // إسناد القيمة يحسب خطوة

    return s;      // إرجاع القيمة يحسب خطوة

    // Big-O مجموع الأوامر التي ستتنفذ هو 4 و لكن بما أنها مجرد أوامر عادية لا تتكرر أكثر من مرة فإنها لا تحسب إطلاقاً في معادلة الـ
    
}

طريقة تقييم أداء الكود

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) فهذا يعني أنه جيد و مقبول.
ملاحظة: إذا كان تقييم الكود جيد و لكن يمكن كتابته بطريقة أخرى أكثر بساطة و لا تتطلب استخدام حلقة, فالأولى أن نقوم بالتخلي عن الحلقة و اعتماد تلك الطريقة.

المثال الأول

Python
Java
C#
C++
C
# تعريف الدالة لا يحسب كخطوة
def func(n):

    # كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0
    
    # Big-O ضمن نتيجة الـ n سنضع المتغير - n أي على حسب القيمة التي نضعها في - (n times) بما أنه عندنا حلقة تنفذ الكود الموضوع فيها
    for i in range(1, n + 1):
        s += i

    # كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s
// تعريف الدالة لا يحسب كخطوة
public int func(int n)
{
    // تعريف المتغيرات لا يحسب إطلاقاً
    int s;
    
    // كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0;
    
    // Big-O ضمن نتيجة الـ n سنضع المتغير - n أي على حسب القيمة التي نضعها في - (n times) بما أنه عندنا حلقة تنفذ الكود الموضوع فيها
    for (int i = 1; i <= n; i++)
    {
        s += i;
    }

    // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s;
    
}
// تعريف الدالة لا يحسب كخطوة
public int Func(int n)
{
    // تعريف المتغيرات لا يحسب إطلاقاً
    int s;
    
    // كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0;
    
    // Big-O ضمن نتيجة الـ n سنضع المتغير - n أي على حسب القيمة التي نضعها في - (n times) بما أنه عندنا حلقة تنفذ الكود الموضوع فيها
    for (int i = 1; i <= n; i++)
    {
        s += i;
    }

    // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s;
    
}
// تعريف الدالة لا يحسب كخطوة
int func(int n)
{
    // تعريف المتغيرات لا يحسب إطلاقاً
    int s;
    
    // كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0;
    
    // Big-O ضمن نتيجة الـ n سنضع المتغير - n أي على حسب القيمة التي نضعها في - (n times) بما أنه عندنا حلقة تنفذ الكود الموضوع فيها
    for (int i = 1; i <= n; i++)
    {
        s += i;
    }

    // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s;
    
}
// تعريف الدالة لا يحسب كخطوة
int func(int n)
{
    // تعريف المتغيرات لا يحسب إطلاقاً
    int s;
    
    // كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0;
    
    // Big-O ضمن نتيجة الـ n سنضع المتغير - n أي على حسب القيمة التي نضعها في - (n times) بما أنه عندنا حلقة تنفذ الكود الموضوع فيها
    for (int i = 1; i <= n; i++)
    {
        s += i;
    }

    // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s;
    
}

طريقة تقييم أداء الكود

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 لا تزال مجهولة سواء كانت مقسومة أم لا و هذا ما سنراه في المثال التالي.

المثال الثاني

Python
Java
C#
C++
C
# تعريف الدالة لا يحسب كخطوة
def func(n):

    # كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0
    
    # Big-O ضمن نتيجة الـ n سنضع المتغير - n أي على حسب القيمة التي نضعها في - (n times) بما أنه عندنا حلقة تنفذ الكود الموضوع فيها
    for i in range(1, int((n + 1) / 2)):
        s += i

    # كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s
// تعريف الدالة لا يحسب كخطوة
public int func(int n)
{
    // تعريف المتغيرات لا يحسب إطلاقاً
    int s;
    
    // كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0;
    
    // Big-O ضمن نتيجة الـ n سنضع المتغير - n أي على حسب القيمة التي نضعها في - (n times) بما أنه عندنا حلقة تنفذ الكود الموضوع فيها
    for (int i = 1; i <= n / 2; i++)
    {
        s += i;
    }
    
    // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s;
}
// تعريف الدالة لا يحسب كخطوة
public int Func(int n)
{
    // تعريف المتغيرات لا يحسب إطلاقاً
    int s;

    // كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0;

    // Big-O ضمن نتيجة الـ n سنضع المتغير - n أي على حسب القيمة التي نضعها في - (n times) بما أنه عندنا حلقة تنفذ الكود الموضوع فيها
    for (int i = 1; i <= n / 2; i++)
    {
        s += i;
    }

    // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s;
}
// تعريف الدالة لا يحسب كخطوة
int func(int n)
{
    // تعريف المتغيرات لا يحسب إطلاقاً
    int s;

    // كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0;

    // Big-O ضمن نتيجة الـ n سنضع المتغير - n أي على حسب القيمة التي نضعها في - (n times) بما أنه عندنا حلقة تنفذ الكود الموضوع فيها
    for (int i = 1; i <= n / 2; i++)
    {
        s += i;
    }

    // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s;
}
// تعريف الدالة لا يحسب كخطوة
int func(int n)
{
    // تعريف المتغيرات لا يحسب إطلاقاً
    int s;

    // كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0;

    // Big-O ضمن نتيجة الـ n سنضع المتغير - n أي على حسب القيمة التي نضعها في - (n times) بما أنه عندنا حلقة تنفذ الكود الموضوع فيها
    for (int i = 1; i <= n / 2; i++)
    {
        s += i;
    }

    // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s;
}

طريقة تقييم أداء الكود

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) تظل نفسها في كلا الحالتين و هذا ما سنراه في المثال التالي.

المثال الثالث

Python
Java
C#
C++
C
# تعريف الدالة لا يحسب كخطوة
def func(n):

    # كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0

    # Big-O ضمن نتيجة الـ n سنضع المتغير - n أي على حسب القيمة التي نضعها في - (n times) بما أنه عندنا حلقة تنفذ الكود الموضوع فيها
    for i in range(n, 0, -1):
        s += i
    
    # كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s
// تعريف الدالة لا يحسب كخطوة
public int func(int n)
{
    // تعريف المتغيرات لا يحسب إطلاقاً
    int s;
    
    // كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0;
    
    // Big-O ضمن نتيجة الـ n سنضع المتغير - n أي على حسب القيمة التي نضعها في - (n times) بما أنه عندنا حلقة تنفذ الكود الموضوع فيها
    for (int i = n, i > 0; i--)
    {
        s += i;
    }

    // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s;
}
// تعريف الدالة لا يحسب كخطوة
public int Func(int n)
{
    // تعريف المتغيرات لا يحسب إطلاقاً
    int s;

    // كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0;

    // Big-O ضمن نتيجة الـ n سنضع المتغير - n أي على حسب القيمة التي نضعها في - (n times) بما أنه عندنا حلقة تنفذ الكود الموضوع فيها
    for (int i = n, i > 0; i--)
    {
        s += i;
    }

    // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s;
}
// تعريف الدالة لا يحسب كخطوة
int func(int n)
{
    // تعريف المتغيرات لا يحسب إطلاقاً
    int s;

    // كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0;

    // Big-O ضمن نتيجة الـ n سنضع المتغير - n أي على حسب القيمة التي نضعها في - (n times) بما أنه عندنا حلقة تنفذ الكود الموضوع فيها
    for (int i = n, i > 0; i--)
    {
        s += i;
    }

    // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s;
}
// تعريف الدالة لا يحسب كخطوة
int func(int n)
{
    // تعريف المتغيرات لا يحسب إطلاقاً
    int s;

    // كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0;

    // Big-O ضمن نتيجة الـ n سنضع المتغير - n أي على حسب القيمة التي نضعها في - (n times) بما أنه عندنا حلقة تنفذ الكود الموضوع فيها
    for (int i = n, i > 0; i--)
    {
        s += i;
    }

    // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s;
}

طريقة تقييم أداء الكود

Execution Steps = 1 + n + 1
Execution Steps = 2 + n

Big O of 2 + n ==> O(n)

ماذا لو كانت الحلقة تتنفذ عدد مرات محدد, هل ستتغير المعادلة؟
طبعاً لأن شرط المعادلة الأساسي لتكون O(n) هو أن يكون عدد المرات التي سيتنفذ فيها الكود مجهولاً.
إذا كان عدد المرات الذي ستكرر فيه الحلقة معروفاً, فإن تقييم الخوارزمية سيكون O(1) لأنه عدد المرات التي سيتنفذ فيها الكود ثابت لا يتغير و هذا ما سنراه في المثال التالي.

المثال الرابع

Python
Java
C#
C++
C
# تعريف الدالة لا يحسب كخطوة
def func(n):

    # كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0
    
    # في الحلقة التالية يوجد أمر واحد سيتنفذ 5 مرات بالضبط (عدد التكرار معروف), أي سيتم حساب الأمر الموضوع كخمس خطوات عادية
    for i in range(5):
        s += i
    
    # كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s
// تعريف الدالة لا يحسب كخطوة
public int func(int n)
{
    // تعريف المتغيرات لا يحسب إطلاقاً
    int s;
    
    // كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0;
    
    // Big-O ضمن نتيجة الـ n سنضع المتغير - n أي على حسب القيمة التي نضعها في - (n times) بما أنه عندنا حلقة تنفذ الكود الموضوع فيها
    for (int i = 1; i <= 5; i++)
    {
        s += i;
    }

    // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s;
}
// تعريف الدالة لا يحسب كخطوة
public int Func(int n)
{
    // تعريف المتغيرات لا يحسب إطلاقاً
    int s;
 
    // كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0;

    // Big-O ضمن نتيجة الـ n سنضع المتغير - n أي على حسب القيمة التي نضعها في - (n times) بما أنه عندنا حلقة تنفذ الكود الموضوع فيها
    for (int i = 1; i <= 5; i++)
    {
        s += i;
    }

    // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s;
}
// تعريف الدالة لا يحسب كخطوة
int func(int n)
{
    // تعريف المتغيرات لا يحسب إطلاقاً
    int s;

    // كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0;

    // Big-O ضمن نتيجة الـ n سنضع المتغير - n أي على حسب القيمة التي نضعها في - (n times) بما أنه عندنا حلقة تنفذ الكود الموضوع فيها
    for (int i = 1; i <= 5; i++)
    {
        s += i;
    }

    // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s;
}
// تعريف الدالة لا يحسب كخطوة
int func(int n)
{
    // تعريف المتغيرات لا يحسب إطلاقاً
    int s;

    // كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0;

    // Big-O ضمن نتيجة الـ n سنضع المتغير - n أي على حسب القيمة التي نضعها في - (n times) بما أنه عندنا حلقة تنفذ الكود الموضوع فيها
    for (int i = 1; i <= 5; i++)
    {
        s += i;
    }

    // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s;
}

طريقة تقييم أداء الكود

Execution Steps = 1 + 5 + 1
Execution Steps = 7

Big O of any constant ==> O(1)

مفهوم المعادلة O(log n)

المقصود بالمعادلة log n هو عندما تتغير قيمة عداد الحلقة بشكل مضاعف أو مقسوم.

المثال الأول

في المثال التالي قمنا بجعل عدّاد الحلقة يتم ضربه بإثنين في كل دورة.

Python
Java
C#
C++
C
# تعريف الدالة لا يحسب كخطوة
def func(n):

    # كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0
    
    # Big-O ضمن نتيجة الـ log n و بنفس الوقت العداد يتم مضاعفة قيمته في كل دورة, سنضع n بما أنه عندنا حلقة تنفذ الكود الموضوع فيها على حسب قيمة
    i = 1
    while i <= n:
        s += i
        i *= 2

    # كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s
// تعريف الدالة لا يحسب كخطوة
public int func(int n)
{
    // تعريف المتغيرات لا يحسب إطلاقاً
    int s;
    
    // كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0;
    
    // Big-O ضمن نتيجة الـ log n و بنفس الوقت العداد يتم مضاعفة قيمته في كل دورة, سنضع n بما أنه عندنا حلقة تنفذ الكود الموضوع فيها على حسب قيمة
    for (int i = 1; i <= n; i *= 2)
    {
        s += i;
    }

    // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s;
    
}
// تعريف الدالة لا يحسب كخطوة
public int Func(int n)
{
    // تعريف المتغيرات لا يحسب إطلاقاً
    int s;
    
    // كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0;
    
    // Big-O ضمن نتيجة الـ log n و بنفس الوقت العداد يتم مضاعفة قيمته في كل دورة, سنضع n بما أنه عندنا حلقة تنفذ الكود الموضوع فيها على حسب قيمة
    for (int i = 1; i <= n; i *= 2)
    {
        s += i;
    }

    // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s;
    
}
// تعريف الدالة لا يحسب كخطوة
int func(int n)
{
    // تعريف المتغيرات لا يحسب إطلاقاً
    int s;
    
    // كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0;
    
    // Big-O ضمن نتيجة الـ log n و بنفس الوقت العداد يتم مضاعفة قيمته في كل دورة, سنضع n بما أنه عندنا حلقة تنفذ الكود الموضوع فيها على حسب قيمة
    for (int i = 1; i <= n; i *= 2)
    {
        s += i;
    }

    // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s;
    
}
// تعريف الدالة لا يحسب كخطوة
int func(int n)
{
    // تعريف المتغيرات لا يحسب إطلاقاً
    int s;
    
    // كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0;
    
    // Big-O ضمن نتيجة الـ log n و بنفس الوقت العداد يتم مضاعفة قيمته في كل دورة, سنضع n بما أنه عندنا حلقة تنفذ الكود الموضوع فيها على حسب قيمة
    for (int i = 1; i <= n; i *= 2)
    {
        s += i;
    }

    // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s;
    
}

طريقة تقييم أداء الكود

Execution Steps = 1 + log n + 1
Execution Steps = 2 + log n

Big O of 2 + log n ==> O(log n)

المثال الثاني

في المثال التالي قمنا بجعل عدّاد الحلقة يتم قسمته على اثنين في كل دورة.

Python
Java
C#
C++
C
# تعريف الدالة لا يحسب كخطوة
def func(n):

    # كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0
    
    # Big-O ضمن نتيجة الـ log n و بنفس الوقت العداد يتم قسمة قيمته في كل دورة, سنضع n بما أنه عندنا حلقة تنفذ الكود الموضوع فيها على حسب قيمة
    i = n
    while i >= 1:
        s += i
        i /= 2

    # كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s
// تعريف الدالة لا يحسب كخطوة
public int func(int n)
{
    // تعريف المتغيرات لا يحسب إطلاقاً
    int s;
    
    // كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0;
    
    // Big-O ضمن نتيجة الـ log n و بنفس الوقت العداد يتم قسمة قيمته في كل دورة, سنضع n بما أنه عندنا حلقة تنفذ الكود الموضوع فيها على حسب قيمة
    for (int i = n; i >= 1; i /= 2)
    {
        s += i;
    }

    // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s;
    
}
// تعريف الدالة لا يحسب كخطوة
public int Func(int n)
{
    // تعريف المتغيرات لا يحسب إطلاقاً
    int s;
    
    // كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0;
    
    // Big-O ضمن نتيجة الـ log n و بنفس الوقت العداد يتم قسمة قيمته في كل دورة, سنضع n بما أنه عندنا حلقة تنفذ الكود الموضوع فيها على حسب قيمة
    for (int i = n; i >= 1; i /= 2)
    {
        s += i;
    }

    // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s;
    
}
// تعريف الدالة لا يحسب كخطوة
int func(int n)
{
    // تعريف المتغيرات لا يحسب إطلاقاً
    int s;
    
    // كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0;
    
    // Big-O ضمن نتيجة الـ log n و بنفس الوقت العداد يتم قسمة قيمته في كل دورة, سنضع n بما أنه عندنا حلقة تنفذ الكود الموضوع فيها على حسب قيمة
    for (int i = n; i >= 1; i /= 2)
    {
        s += i;
    }

    // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s;
    
}
// تعريف الدالة لا يحسب كخطوة
int func(int n)
{
    // تعريف المتغيرات لا يحسب إطلاقاً
    int s;
    
    // كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0;
    
    // Big-O ضمن نتيجة الـ log n و بنفس الوقت العداد يتم قسمة قيمته في كل دورة, سنضع n بما أنه عندنا حلقة تنفذ الكود الموضوع فيها على حسب قيمة
    for (int i = n; i >= 1; i /= 2)
    {
        s += i;
    }

    // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s;
    
}

طريقة تقييم أداء الكود

Execution Steps = 1 + log n + 1
Execution Steps = 2 + log n

Big O of 2 + log n ==> O(log n)

مفهوم المعادلة O(n^k)

المقصود بالحرف n هو أن الكود موضوع بداخل حلقة.
المقصود بالحرف k أن الحلقة تحتوي أيضاً على حلقة أو أكثر بشكل متداخل ( Nested Loop ).

عند وضع التقييم للكود, الحرف n نضعه كما هو ليشير أنه يوجد حلقة, أما الحرف k فنضع مكانه عدد الحلقات المتداخلة و إليك بعض الأمثلة:

إذا كان الكود يتضمن حلقتين متداخلتين نكتب O(n²)
إذا كان الكود يتضمن ثلاث حلقات متداخلة نكتب O(n³)
إذا كان الكود يتضمن أربع حلقات متداخلة نكتب O(n⁴) و هكذا.

لا تقلق ستتضح لك الفكرة من الأمثلة.

المثال الأول

في المثال التالي قمنا بوضع حلقة بداخل حلقة.

Python
Java
C#
C++
C
# تعريف الدالة لا يحسب كخطوة
def func(n):

    # كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0
    
    # (n لأنها تبدأ من 1 إلى) n الحلقة الخارجية سيتم تمثيلها بـ
    for i in range(1, n):
        # (n لأنها تبدأ من 1 إلى) n الحلقة الداخلية سيتم تمثيلها بـ
        for j in range(1, n):
            # n * n الأمر الموضوع في هاتين الحلقتين المتداخلتين سيتم تكراره بمقدار قيمة
            s += j

    # كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s
// تعريف الدالة لا يحسب كخطوة
public int func(int n)
{
    // تعريف المتغيرات لا يحسب إطلاقاً
    int s;
    
    // كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0;
    
    // (n لأنها تبدأ من 1 إلى) n الحلقة الخارجية سيتم تمثيلها بـ
    for (int i = 1; i <= n; i++) {
        // (n لأنها تبدأ من 1 إلى) n الحلقة الداخلية سيتم تمثيلها بـ
        for (int j = 1; j <= n; j++) {
            // n * n الأمر الموضوع في هاتين الحلقتين المتداخلتين سيتم تكراره بمقدار قيمة
            s += j;
        }
    }

    // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s;
    
}
// تعريف الدالة لا يحسب كخطوة
public int Func(int n)
{
    // تعريف المتغيرات لا يحسب إطلاقاً
    int s;
    
    // كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0;
    
    // (n لأنها تبدأ من 1 إلى) n الحلقة الخارجية سيتم تمثيلها بـ
    for (int i = 1; i <= n; i++) {
        // (n لأنها تبدأ من 1 إلى) n الحلقة الداخلية سيتم تمثيلها بـ
        for (int j = 1; j <= n; j++) {
            // n * n الأمر الموضوع في هاتين الحلقتين المتداخلتين سيتم تكراره بمقدار قيمة
            s += j;
        }
    }

    // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s;
    
}
// تعريف الدالة لا يحسب كخطوة
int func(int n)
{
    // تعريف المتغيرات لا يحسب إطلاقاً
    int s;
    
    // كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0;
    
    // (n لأنها تبدأ من 1 إلى) n الحلقة الخارجية سيتم تمثيلها بـ
    for (int i = 1; i <= n; i++) {
        // (n لأنها تبدأ من 1 إلى) n الحلقة الداخلية سيتم تمثيلها بـ
        for (int j = 1; j <= n; j++) {
            // n * n الأمر الموضوع في هاتين الحلقتين المتداخلتين سيتم تكراره بمقدار قيمة
            s += j;
        }
    }

    // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s;
    
}
// تعريف الدالة لا يحسب كخطوة
int func(int n)
{
    // تعريف المتغيرات لا يحسب إطلاقاً
    int s;
    
    // كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0;
    
    // (n لأنها تبدأ من 1 إلى) n الحلقة الخارجية سيتم تمثيلها بـ
    for (int i = 1; i <= n; i++) {
        // (n لأنها تبدأ من 1 إلى) n الحلقة الداخلية سيتم تمثيلها بـ
        for (int j = 1; j <= n; j++) {
            // n * n الأمر الموضوع في هاتين الحلقتين المتداخلتين سيتم تكراره بمقدار قيمة
            s += j;
        }
    }

    // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s;
    
}

طريقة تقييم أداء الكود

Execution Steps = 1 + n * n + 1
Execution Steps = 2 + n^2

Big O of 2 + n^2 ==> O(n^2)

المثال الثاني

في المثال التالي قمنا بوضع ثلاث حلقات متداخلة.

Python
Java
C#
C++
C
# تعريف الدالة لا يحسب كخطوة
def func(n):

    # كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0
    
    # (n لأنها تبدأ من 1 إلى) n الحلقة الأولى سيتم تمثيلها بـ
    for i in range(1, n):
        # (n لأنها تبدأ من 1 إلى) n الحلقة الثانية سيتم تمثيلها بـ
        for j in range(1, n):
            # (n لأنها تبدأ من 1 إلى) n الحلقة الثالثة سيتم تمثيلها بـ
            for k in range(1, n):
                # n * n * n الأمر الموضوع في هذه الحلقات المتدخلة سيتم تكراره بمقدار قيمة
                s += j

    # كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s
// تعريف الدالة لا يحسب كخطوة
public int func(int n)
{
    // تعريف المتغيرات لا يحسب إطلاقاً
    int s;
    
    // كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0;
    
    // (n لأنها تبدأ من 1 إلى) n الحلقة الأولى سيتم تمثيلها بـ
    for (int i = 1; i <= n; i++) {
        // (n لأنها تبدأ من 1 إلى) n الحلقة الثانية سيتم تمثيلها بـ
        for (int j = 1; j <= n; j++) {
            // (n لأنها تبدأ من 1 إلى) n الحلقة الثالثة سيتم تمثيلها بـ
            for (int k = 1; k <= n; k++) {
                // n * n * n الأمر الموضوع في هذه الحلقات المتدخلة سيتم تكراره بمقدار قيمة
                s += j
            }
        }
    }

    // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s;
    
}
// تعريف الدالة لا يحسب كخطوة
public int Func(int n)
{
    // تعريف المتغيرات لا يحسب إطلاقاً
    int s;
    
    // كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0;
    
    // (n لأنها تبدأ من 1 إلى) n الحلقة الأولى سيتم تمثيلها بـ
    for (int i = 1; i <= n; i++) {
        // (n لأنها تبدأ من 1 إلى) n الحلقة الثانية سيتم تمثيلها بـ
        for (int j = 1; j <= n; j++) {
            // (n لأنها تبدأ من 1 إلى) n الحلقة الثالثة سيتم تمثيلها بـ
            for (int k = 1; k <= n; k++) {
                // n * n * n الأمر الموضوع في هذه الحلقات المتدخلة سيتم تكراره بمقدار قيمة
                s += j
            }
        }
    }

    // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s;
    
}
// تعريف الدالة لا يحسب كخطوة
int func(int n)
{
    // تعريف المتغيرات لا يحسب إطلاقاً
    int s;
    
    // كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0;
    
    // (n لأنها تبدأ من 1 إلى) n الحلقة الأولى سيتم تمثيلها بـ
    for (int i = 1; i <= n; i++) {
        // (n لأنها تبدأ من 1 إلى) n الحلقة الثانية سيتم تمثيلها بـ
        for (int j = 1; j <= n; j++) {
            // (n لأنها تبدأ من 1 إلى) n الحلقة الثالثة سيتم تمثيلها بـ
            for (int k = 1; k <= n; k++) {
                // n * n * n الأمر الموضوع في هذه الحلقات المتدخلة سيتم تكراره بمقدار قيمة
                s += j
            }
        }
    }

    // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s;
    
}
// تعريف الدالة لا يحسب كخطوة
int func(int n)
{
    // تعريف المتغيرات لا يحسب إطلاقاً
    int s;
    
    // كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0;
    
    // (n لأنها تبدأ من 1 إلى) n الحلقة الأولى سيتم تمثيلها بـ
    for (int i = 1; i <= n; i++) {
        // (n لأنها تبدأ من 1 إلى) n الحلقة الثانية سيتم تمثيلها بـ
        for (int j = 1; j <= n; j++) {
            // (n لأنها تبدأ من 1 إلى) n الحلقة الثالثة سيتم تمثيلها بـ
            for (int k = 1; k <= n; k++) {
                // n * n * n الأمر الموضوع في هذه الحلقات المتدخلة سيتم تكراره بمقدار قيمة
                s += j
            }
        }
    }

    // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s;
    
}

طريقة تقييم أداء الكود

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).

مثال

Python
Java
C#
C++
C
# تعريف الدالة لا يحسب كخطوة
def func(n):

    # كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0
    
    # (n لأنها تبدأ من 1 إلى) n الحلقة الخارجية سيتم تمثيلها بـ
    for i in range(1, n):
        # لأن العداد يتم مضاعفة قيمته في كل دورة log n الحلقة الداخلية سيتم تمثيلها بـ
        j = 1
        while j <= n:
            # n * n الأمر الموضوع في هاتين الحلقتين المتداخلتين سيتم تكراره بمقدار قيمة
            s += j
            j *= 2

    # كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s
// تعريف الدالة لا يحسب كخطوة
public int func(int n)
{
    // تعريف المتغيرات لا يحسب إطلاقاً
    int s;
    
    // كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0;
    
    // (n لأنها تبدأ من 1 إلى) n الحلقة الخارجية سيتم تمثيلها بـ
    for (int i = 1; i <= n; i++) {
        // أن العداد يتم مضاعفة قيمته في كل دورة log n الحلقة الداخلية سيتم تمثيلها بـ
        for (int j = 1; j <= n; j *= 2) {
            // n * n الأمر الموضوع في هاتين الحلقتين المتداخلتين سيتم تكراره بمقدار قيمة
            s += j;
        }
    }

    // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s;
    
}
// تعريف الدالة لا يحسب كخطوة
public int Func(int n)
{
    // تعريف المتغيرات لا يحسب إطلاقاً
    int s;
    
    // كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0;
    
    // (n لأنها تبدأ من 1 إلى) n الحلقة الخارجية سيتم تمثيلها بـ
    for (int i = 1; i <= n; i++) {
        // أن العداد يتم مضاعفة قيمته في كل دورة log n الحلقة الداخلية سيتم تمثيلها بـ
        for (int j = 1; j <= n; j *= 2) {
            // n * n الأمر الموضوع في هاتين الحلقتين المتداخلتين سيتم تكراره بمقدار قيمة
            s += j;
        }
    }

    // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s;
    
}
// تعريف الدالة لا يحسب كخطوة
int func(int n)
{
    // تعريف المتغيرات لا يحسب إطلاقاً
    int s;
    
    // كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0;
    
    // (n لأنها تبدأ من 1 إلى) n الحلقة الخارجية سيتم تمثيلها بـ
    for (int i = 1; i <= n; i++) {
        // أن العداد يتم مضاعفة قيمته في كل دورة log n الحلقة الداخلية سيتم تمثيلها بـ
        for (int j = 1; j <= n; j *= 2) {
            // n * n الأمر الموضوع في هاتين الحلقتين المتداخلتين سيتم تكراره بمقدار قيمة
            s += j;
        }
    }

    // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s;
    
}
// تعريف الدالة لا يحسب كخطوة
int func(int n)
{
    // تعريف المتغيرات لا يحسب إطلاقاً
    int s;
    
    // كما قلنا سابقاً Big-O إسناد أي قيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    s = 0;
    
    // (n لأنها تبدأ من 1 إلى) n الحلقة الخارجية سيتم تمثيلها بـ
    for (int i = 1; i <= n; i++) {
        // أن العداد يتم مضاعفة قيمته في كل دورة log n الحلقة الداخلية سيتم تمثيلها بـ
        for (int j = 1; j <= n; j *= 2) {
            // n * n الأمر الموضوع في هاتين الحلقتين المتداخلتين سيتم تكراره بمقدار قيمة
            s += j;
        }
    }

    // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return s;
    
}

طريقة تقييم أداء الكود

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.
ملاحظة: الكود الموضوع في المثال التالي تم شرحه بتفصيل ممل في دورة أساسيات البرمجة و بالتحديد في درس الإستدعاء الذاتي.

مثال

Python
Java
C#
C++
C
# تعريف الدالة لا يحسب كخطوة
def factorial(n):

    # الشرط بحد ذاته لا يحسب خطوة
    if n > 0:
        # كخطوة return لنفسها ) سيتم حساب أمر الـ return كل مرة سيتم فيها إعادة استدعاء الدالة لنفسها, ( أي ستفعل
        # n! فإنه سيتم تمثيلها n بما أن الدالة ستعيد استدعاء نفسها بمقدار قيمة
        return n * factorial(n - 1)

    # كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return 1
// تعريف الدالة لا يحسب كخطوة
public int factorial(int n)
{
    // الشرط بحد ذاته لا يحسب خطوة
    if (n > 0)
    {
        // كخطوة return لنفسها ) سيتم حساب أمر الـ return كل مرة سيتم فيها إعادة استدعاء الدالة لنفسها, ( أي ستفعل
        // n! فإنه سيتم تمثيلها n بما أن الدالة ستعيد استدعاء نفسها بمقدار قيمة
        return n * factorial(n - 1);
    }

    // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return 1;
}
// تعريف الدالة لا يحسب كخطوة
public int Factorial(int n)
{
    // الشرط بحد ذاته لا يحسب خطوة
    if (n > 0)
    {
        // كخطوة return لنفسها ) سيتم حساب أمر الـ return كل مرة سيتم فيها إعادة استدعاء الدالة لنفسها, ( أي ستفعل
        // n! فإنه سيتم تمثيلها n بما أن الدالة ستعيد استدعاء نفسها بمقدار قيمة
        return n * Factorial(n - 1);
    }

    // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return 1;
}
// تعريف الدالة لا يحسب كخطوة
int factorial(int n)
{
    // الشرط بحد ذاته لا يحسب خطوة
    if (n > 0)
    {
        // كخطوة return لنفسها ) سيتم حساب أمر الـ return كل مرة سيتم فيها إعادة استدعاء الدالة لنفسها, ( أي ستفعل
        // n! فإنه سيتم تمثيلها n بما أن الدالة ستعيد استدعاء نفسها بمقدار قيمة
        return n * factorial(n - 1);
    }

    // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return 1;
}
// تعريف الدالة لا يحسب كخطوة
int factorial(int n)
{
    // الشرط بحد ذاته لا يحسب خطوة
    if (n > 0)
    {
        // كخطوة return لنفسها ) سيتم حساب أمر الـ return كل مرة سيتم فيها إعادة استدعاء الدالة لنفسها, ( أي ستفعل
        // n! فإنه سيتم تمثيلها n بما أن الدالة ستعيد استدعاء نفسها بمقدار قيمة
        return n * factorial(n - 1);
    }

    // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
    return 1;
}

طريقة تقييم أداء الكود

Execution Steps = n! + 1

Big O of n! + 1 ==> O(n!)

مفهوم المعادلة O(kⁿ)

المقصود بهذه المعادلة أن الدالة ستعيد إستدعاء نفسها بمقدار قيمة n و في كل عملية إستدعاء سيتم استدعاءها بشكل مضاعف أيضاً.

فعلى سبيل المثال, أول مرة تستدعي فيها نفسها, تقوم باستدعاء نفسها مرتين بشكل متوازي.
ثاني مرة تستدعي فيها نفسها, تقوم باستدعاء نفسها 4 مرات بشكل متوازي.
ثالث مرة تستدعي فيها نفسها, تقوم باستدعاء نفسها 8 مرات بشكل متوازي.
رابع مرة تستدعي فيها نفسها, تقوم باستدعاء نفسها 16 مرة بشكل متوازي و هكذا.

مثال

في المثال التالي سنقوم بتطبيق مبدأ يسمى فايبوناتشي ( Fibonacci ).
بكل صراحة فكرة هذا المبدأ تعتبر بسيطة جداً و لكن تطبيقه بهذا الأسلوب سيكون غريب بالنسبة لك و لقد تعمدنا كتابته بهذا الشكل حتى نستخدم المعادلة O(kⁿ)
بشكل عام فكرة الكود أنك في كل مرة ستجمع القيمة ما قبل الأخيرة مع القيمة الأخيرة و تضع الناتج بعدهما كما في الصورة التالية.

Python
Java
C#
C++
C
# تعريف الدالة لا يحسب كخطوة
def fibonacci(n):

    # الشرط بحد ذاته لا يحسب خطوة
    if n <= 0:
        # كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
        return 0

    # الشرط بحد ذاته لا يحسب خطوة
    if n <= 2:
        # كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
        return 1
        
    # كخطوتين return لنفسها ) سيتم حساب أمر الـ return كل مرة سيتم فيها إعادة استدعاء الدالة لنفسها, ( أي ستفعل
    # n و السبب في ذلك أن كل عملية جمع سيتم إرجاعها تتطلب من الدالة أن تستدعي نفسها مرتين مضاعفة بقيمة
    # O(k^n) بما أن الدالة ستعيد استدعاء نفسها كل مرة بمقدار ضعفين زيادة فإنه سيتم تمثيلها بـ
    return fibonacci(n - 1) + fibonacci(n - 2)
// تعريف الدالة لا يحسب كخطوة
public int fibonacci(int n)
{
    // الشرط بحد ذاته لا يحسب خطوة
    if (n <= 0)
    {
        // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
        return 0;
    }
    
    // الشرط بحد ذاته لا يحسب خطوة
    if (n <= 2)
    {
        // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
        return 1;
    }

    // كخطوتين return لنفسها ) سيتم حساب أمر الـ return كل مرة سيتم فيها إعادة استدعاء الدالة لنفسها, ( أي ستفعل
    // n و السبب في ذلك أن كل عملية جمع سيتم إرجاعها تتطلب من الدالة أن تستدعي نفسها مرتين مضاعفة بقيمة
    // O(k^n) بما أن الدالة ستعيد استدعاء نفسها كل مرة بمقدار ضعفين زيادة فإنه سيتم تمثيلها بـ
    return fibonacci(n - 1) + fibonacci(n - 2);
}
// تعريف الدالة لا يحسب كخطوة
public int Fibonacci(int n)
{
    // الشرط بحد ذاته لا يحسب خطوة
    if (n <= 0)
    {
        // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
        return 0;
    }
    
    // الشرط بحد ذاته لا يحسب خطوة
    if (n <= 2)
    {
        // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
        return 1;
    }

    // كخطوتين return لنفسها ) سيتم حساب أمر الـ return كل مرة سيتم فيها إعادة استدعاء الدالة لنفسها, ( أي ستفعل
    // n و السبب في ذلك أن كل عملية جمع سيتم إرجاعها تتطلب من الدالة أن تستدعي نفسها مرتين مضاعفة بقيمة
    // O(k^n) بما أن الدالة ستعيد استدعاء نفسها كل مرة بمقدار ضعفين زيادة فإنه سيتم تمثيلها بـ
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}
// تعريف الدالة لا يحسب كخطوة
int fibonacci(int n)
{
    // الشرط بحد ذاته لا يحسب خطوة
    if (n <= 0)
    {
        // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
        return 0;
    }
    
    // الشرط بحد ذاته لا يحسب خطوة
    if (n <= 2)
    {
        // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
        return 1;
    }

    // كخطوتين return لنفسها ) سيتم حساب أمر الـ return كل مرة سيتم فيها إعادة استدعاء الدالة لنفسها, ( أي ستفعل
    // n و السبب في ذلك أن كل عملية جمع سيتم إرجاعها تتطلب من الدالة أن تستدعي نفسها مرتين مضاعفة بقيمة
    // O(k^n) بما أن الدالة ستعيد استدعاء نفسها كل مرة بمقدار ضعفين زيادة فإنه سيتم تمثيلها بـ
    return fibonacci(n - 1) + fibonacci(n - 2);
}
// تعريف الدالة لا يحسب كخطوة
int fibonacci(int n)
{
    // الشرط بحد ذاته لا يحسب خطوة
    if (n <= 0)
    {
        // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
        return 0;
    }
    
    // الشرط بحد ذاته لا يحسب خطوة
    if (n <= 2)
    {
        // كما قلنا سابقاً Big-O إرجاع القيمة يحسب خطوة واحدة و لكن عدد الخطوات غير مهم في تقييم الـ
        return 1;
    }

    // كخطوتين return لنفسها ) سيتم حساب أمر الـ return كل مرة سيتم فيها إعادة استدعاء الدالة لنفسها, ( أي ستفعل
    // n و السبب في ذلك أن كل عملية جمع سيتم إرجاعها تتطلب من الدالة أن تستدعي نفسها مرتين مضاعفة بقيمة
    // O(k^n) بما أن الدالة ستعيد استدعاء نفسها كل مرة بمقدار ضعفين زيادة فإنه سيتم تمثيلها بـ
    return fibonacci(n - 1) + fibonacci(n - 2);
}

طريقة تقييم أداء الكود

Execution Steps = 2^n

Big O of 2^n ==> O(k^n)

الفيديو التالي يشرح طريقة عمل الدالة عند استدعائها و كيف أنها تستدعي نفسها أكثر من مرة في كل عملية إستدعاء.

في الدرس التالي سنضع تمارين يمكن حلها بأكثر من طريقة و لكننا سنعرف أي طريقة هي الأفضل بناءً على تقييم الكود الذي تعلمنا كيف نحسبه في هذا الدرس.

الدرس التالي❯

❮الدرس السابق

تحديات برمجيةحساب الـ Big-O Notation

تقييم أداء الخوارزميات

مفهوم المعادلة O(1)

مثال

مفهوم المعادلة O(n)

المثال الأول

المثال الثاني

المثال الثالث

المثال الرابع

مفهوم المعادلة O(log n)

المثال الأول

المثال الثاني

مفهوم المعادلة O(n^k)

المثال الأول

المثال الثاني

مفهوم المعادلة O(n log n)

مثال

مفهوم المعادلة O(n!)

مثال

مفهوم المعادلة O(kⁿ)

مثال

هدف الموقع

روابط مهمة

حقوق النشر

الدورات

أدوات مساعدة

أقسام الموقع

إبحث

تحديات برمجيةحساب الـ Big-O Notation

تقييم أداء الخوارزميات

مفهوم المعادلة O(1)

مثال

مفهوم المعادلة O(n)

المثال الأول

المثال الثاني

المثال الثالث

المثال الرابع

مفهوم المعادلة O(log n)

المثال الأول

المثال الثاني

مفهوم المعادلة O(nk)

المثال الأول

المثال الثاني

مفهوم المعادلة O(n log n)

مثال

مفهوم المعادلة O(n!)

مثال

مفهوم المعادلة O(kn)

مثال

هدف الموقع

روابط مهمة

حقوق النشر

الدورات

أدوات مساعدة

أقسام الموقع

إبحث

مفهوم المعادلة O(n^k)

مفهوم المعادلة O(kⁿ)