أمثلة على ترميز Big O: شرح التعقيد الزمني وكفاءة الخوارزميات

ما هو ترميز Big O ولماذا يهم في تحليل الأداء؟

يُستخدم ترميز Big O لوصف الطريقة التي يزداد بها الزمن المتوقع لتنفيذ الخوارزمية عند زيادة حجم البيانات أو المشكلة. هذه الفكرة أساسية في علوم الحاسوب، لأنها تساعد المطوّرين على مقارنة الحلول المختلفة واختيار الخوارزمية الأنسب من حيث السرعة والكفاءة.

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

كيف يصف Big O نمو زمن التنفيذ؟

لفهم الفكرة بصورة أوضح، تخيّل أن لدينا خوارزمية لترتيب قائمة من الأرقام.

حالة الخوارزمية ذات التعقيد O(n)

إذا كانت الخوارزمية تعمل بتعقيد O(n)، فهذا يعني أن زمن التنفيذ يزداد بشكل خطي مع زيادة حجم القائمة. فإذا أصبحت القائمة أكبر بمقدار 10 مرات، فمن المتوقع أن يصبح زمن التنفيذ أكبر بمقدار يقارب 10 مرات أيضاً.

على سبيل المثال، إذا كان ترتيب 10 عناصر يستغرق 4 ثوانٍ، فإن ترتيب 100 عنصر قد يستغرق نحو 40 ثانية.

حالة الخوارزمية ذات التعقيد O(n²)

في هذا النوع، يزداد الزمن بشكل تربيعي. فإذا زاد حجم البيانات 10 مرات، فقد يرتفع زمن التنفيذ إلى نحو 100 مرة.

بمعنى آخر، إذا احتاجت الخوارزمية إلى 4 ثوانٍ لترتيب 10 عناصر، فقد تحتاج إلى نحو 400 ثانية لترتيب 100 عنصر.

حالة الخوارزمية ذات التعقيد O(n log(n))

تُعد هذه الفئة من أسرع التعقيدات الشائعة في خوارزميات الترتيب الفعالة. عند زيادة حجم البيانات 10 مرات، لا يزيد الزمن بنفس قسوة O(n²)، بل قد يرتفع تقريباً إلى 23 مرة.

فإذا استغرق ترتيب 10 عناصر 4 ثوانٍ، فقد يستغرق ترتيب 100 عنصر نحو 92 ثانية.

مثال عملي: فحص ما إذا كان العدد أولياً

بعد فهم المعنى النظري لترميز Big O، لننتقل إلى مثال عملي يوضح كيف نستخدمه في تحليل التعقيد الزمني.

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

الخوارزمية الأولى: فحص جميع القواسم الممكنة

أبسط طريقة هي تجربة كل الأعداد بين 2 وnum - 1. إذا وجدنا عدداً يقسم num دون باقٍ، فالعدد ليس أولياً.

pub fn is_prime_all(num: i64) -> bool {
    // Check for divisors of num
    for i in 2..num {
        if num % i == 0 {
            // Any divisor other than 1 or num means num is not prime
            return false;
        }
    }

    // No other divisors found means num is prime
    return true;
}

تحليل التعقيد الزمني للخوارزمية الأولى

في أسوأ الحالات، نحتاج إلى اختبار نحو num - 2 قيمة قبل التأكد من أن العدد أولي. لذلك يكون التعقيد الزمني هنا هو O(num) أو بصورة أبسط O(n).

في ترميز Big O نهتم بالحد الأكبر فقط، لذلك نتجاهل الثوابت والحدود الصغيرة مثل -2.

نتائج الأداء

• فحص العدد 1789 استغرق في المتوسط 5.9 microseconds.
• فحص العدد 17903 استغرق في المتوسط 60.0 microseconds.

نلاحظ أن العدد الأكبر بعشرة أضعاف تقريباً احتاج زمناً أكبر بنحو عشرة أضعاف أيضاً، وهذا ينسجم مع التعقيد O(n).

الخوارزمية الثانية: فحص نصف القواسم فقط

يمكن تحسين الطريقة السابقة قليلاً. فإذا كان العدد num غير قابل للقسمة على 2، فلا حاجة لفحص أي عدد أكبر من num / 2، لأن أي قاسم أكبر من ذلك لا يمكن أن يُنتج عدداً صحيحاً مناسباً مع عامل آخر أكبر من 1.

pub fn is_prime_half(num: i64) -> bool {
    // Check for divisors of num
    for i in 2..num / 2 {
        if num % i == 0 {
            // Any divisor other than 1 or num means num is not prime
            return false;
        }
    }

    // No other divisors found means num is prime
    return true;
}

هل تغيّر التعقيد الزمني فعلاً؟

رغم أن هذه الخوارزمية تنفّذ عدداً أقل من العمليات، فإنها ما زالت تفحص قيماً تصل إلى حدود مرتبطة مباشرة بـn. فهي تختبر تقريباً num / 2 - 1 قيمة، ولذلك يبقى التعقيد الزمني O(n).

بمعنى أدق، الأداء الفعلي تحسّن بسبب تقليل عدد العمليات، لكن فئة النمو نفسها لم تتغير.

نتائج الأداء

• فحص العدد 1789 استغرق نحو 3.1 microseconds.
• فحص العدد 17903 استغرق نحو 31.1 microseconds.

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

الخوارزمية الثالثة: فحص أزواج القواسم حتى الجذر التربيعي

هنا نصل إلى التحسين الحقيقي. الفكرة تقوم على أن القواسم تأتي في أزواج. فإذا كان i يقسم num، فهناك قيمة مقابلة هي num / i. لذلك لا نحتاج إلى فحص كل الأعداد حتى num / 2، بل يكفي التوقف عند الجذر التربيعي للعدد.

السبب بسيط: إذا تجاوزنا √num، فهذا يعني أن القاسم المقابل سيكون أصغر من √num وقد تم فحصه بالفعل.

pub fn is_prime_sqrt(num: i64) -> bool {
    // Check for divisors of num
    for i in 2..=(num as f64).sqrt() as i64 {
        if num % i == 0 {
            // Any divisor other than 1 or num means num is not prime
            return false;
        }
    }

    // No other divisors found means num is prime
    return true;
}

تحليل التعقيد الزمني للخوارزمية الثالثة

بما أننا نفحص فقط حتى √num، فإن عدد المحاولات يصبح تقريباً √num - 1. لذا فإن التعقيد الزمني لهذه الخوارزمية هو O(√n).

وهذا تحسن مهم جداً مقارنة بـO(n)، خصوصاً عندما نتعامل مع أعداد كبيرة.

نتائج الأداء

• فحص العدد 1789 استغرق نحو 161.9 nanoseconds.
• فحص العدد 17903 استغرق نحو 555.0 nanoseconds.

في هذه الحالة، عندما أصبح العدد أكبر بنحو 10 مرات، ازداد الزمن بحوالي 3.4 مرات فقط، وهو رقم قريب من قيمة √10 ≈ 3.2. وهذا يؤكد دقة التحليل النظري في تقدير نمو زمن التنفيذ.

مقارنة مختصرة بين الخوارزميات الثلاث

لماذا نهتم بتحليل التعقيد الزمني؟

تحليل التعقيد الزمني لا يهدف فقط إلى التفريق بين خوارزمية سريعة وأخرى بطيئة، بل يساعد أيضاً على:

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

ومن المهم الانتباه إلى أن التحسينات الصغيرة في التنفيذ قد تقلل الزمن الفعلي، لكن التأثير الأكبر عادة يأتي من تحسين فئة التعقيد نفسها، مثل الانتقال من O(n) إلى O(√n).

أفضل الممارسات عند قراءة ترميز Big O

1. ركّز على معدل النمو لا على الأرقام الثابتة فقط.
2. ميّز بين التحسين العملي والتحسين البنيوي في الخوارزمية.
3. لا تعتمد على القياس المحلي وحده، لأن نتائج الأجهزة تختلف.
4. استخدم التحليل النظري مع الاختبارات العملية للحصول على صورة دقيقة.

الخلاصة التقنية

ترميز Big O هو أداة أساسية لفهم كفاءة الخوارزميات كلما ازداد حجم الإدخال. في مثال فحص الأعداد الأولية، رأينا أن تقليل عدد العمليات لا يكفي دائماً لتغيير التصنيف العام للأداء، كما حدث بين الخوارزميتين الأولى والثانية. أما التحسين الحقيقي فظهر عند تغيير منطق الفحص نفسه والاعتماد على الجذر التربيعي، ما خفّض التعقيد من O(n) إلى O(√n). تقنياً، هذا المثال يوضح أن التفكير الرياضي في بنية المشكلة غالباً ما ينتج مكاسب أكبر بكثير من مجرد التعديلات السطحية على الكود.