نظرية التعقيد

تحدثنا في المقال السابق عن 7نصائح يقدمها كتاب Competitive Programming لنتائج افضل في المسابقات البرمجية ، و الان سنتحدث عن كيفية تحليل أداء الكود من الناحية الزمنية و من ناحية حجم البرنامج الناتج ، و هو ما يندرج تحت مفهوم  Big O Notation  .
Big O Notation:

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

لنضع بعض الفرضيات التي ستساعدنا في فهم هذه الفكرة :
- لنفترض أن تنفيذ كل تعليمة يحتاج نبضة ساعة واحدة .
- لنفترض أن كل نبضة ساعة تحتاج إلى ثانية واحد .
- و بالتالي كل تعليمة تحتاج إلى ثانية حتى يتم تنفيذها .

كيف يمكننا تحديد التعقيد ؟

·        O(1) : تصف الخوارزمية التي يتم تنفيذها دوما خلال نفس المدة الزمنية (وتحتاج نفس الحجم)

bool IsFirstElementNull(IList<string> elements)

{

return elements [0] == null;

}

·        O(n) : و هي تصف الخوارزمية التي يتزايد زمن تنفيذها خطيا (و كذلك الأمر بالنسبة للحجم )

أي إذا كان لدينا دخل بحجم واحد بايت فالخرج سيكون بحجم واحد بايت ، و اذا كان 2بايت فالخرج أيضا 2 بايت

bool ContainsValue(IList<string> elements, string value)

{

    foreach (var element in elements)

    {

        if (element == value) return true;

    }

    return false;

}

·         O(n²) : و هي تصف الخوارزميات التي يكون تاثير زيادة عنصر على عناصر دخلها هو تاثر تربيعي على الزمن (و كذلك الحجم ).

في المثال التالي لدينا حلقتين For  متداخلتين بحيث n  تمثل عدد تكرارات كل الحلقة ، و بالتالي التعقيد هو : ناتج جداء عدد تكرارات الحلقة الأولى بعدد تكرارات الحلقة الثانية ، و بالتالي الجواب هو n² . لو كان لدينا 3 حلقات بتكرار n لكل حلقة ، فان التعقيد سيكون O(n³) .

مثلا إذا كان لدينا دخل بحجم 2 بايت فالخرج سيكون بحجم 2ⁿ  ، حيث n هو عدد الحلقات المتداخلة . 

bool ContainsDuplicates(IList<string> elements)

{

    for (var outer = 0; outer < elements.Count; outer++)

    {

        for (var inner = 0; inner < elements.Count; inner++)

        {

            // Don't compare with self

            if (outer == inner) continue;

            if (elements[outer] == elements[inner]) return true;

        }

    }

    return false;

}

·         O(2ⁿ) : و هي تعبرعن الخوارزمية التي يكون تاثير زيادة حجم الدخل بمقدار واحد هو ضرب الزمن (أو الحجم) بمقدار 2 ، مثال : فيبوناتشي .

مثلا إذا كانت التعليمة تحتاج الى 3 ثانية فالخرج النهائي يحتاج 2³ ثانية.

int Fibonacci(int number)

{

    if (number <= 1) return number;

    return Fibonacci(number - 2) + Fibonacci(number - 1);

}

·        O(log n) : مثال Binary search  .

جدول يوضح درجة التعقيد لبعض بنى المعطيات :

جدول يوضح درجة التعقيد لبعض خوارزميات الترتيب :