المستوى: مبتدئ

Big O Notation: لغة المبرمجين لقياس سرعة الكود قبل ما يقع

لو كتبت function بتلاقي اسم في قائمة 1000 شخص في ميلي ثانية، وبعد سنتين القائمة بقت 10 مليون والـ function بتاخد 6 دقايق، المشكلة مش في السيرفر. المشكلة إنك ما حسبتش Big O قبل ما تكتب الكود.

المشكلة باختصار

كل مبرمج بيكتب كود بيشتغل تمام على بيانات صغيرة. ولما البيانات تكبر، نفس الكود ممكن يقع أو ياخد أيام. Big O Notation هو الطريقة العلمية اللي بتقولّك "كودك ده هيبطّأ ازاي مع كبر الدخل" — قبل ما تشغّله أصلاً على بيانات حقيقية.

ركّز: Big O مش بيقيس الزمن بالثواني. بيقيس "كيف ينمو عدد العمليات مع كبر البيانات". الفرق ده مهم، هنوضحه بعد المثال.

تخيّل دفتر التليفونات

عندك دفتر تليفونات قديم فيه 1000 اسم ومحتاج تلاقي رقم "أحمد محمد". قدامك طريقتين:

الطريقة الأولى: تفتح أول صفحة وتقرا اسم اسم لحد ما تلاقيه. لو الاسم في الآخر، قريت 1000 سطر. لو الدفتر كبر لـ 10 مليون اسم، قريت 10 مليون سطر. الزمن بيكبر بنفس نسبة كبر الدفتر.

الطريقة الثانية: الدفتر مرتب أبجدي. تفتح في النص بالظبط، تشوف الحرف الموجود، وتقرر تروح يمين ولا شمال. كل خطوة بتقسم البيانات اللي قدامك على 2. مع 1000 اسم، 10 خطوات تكفي. مع 10 مليون، 24 خطوة بس.

الطريقة الأولى اسمها O(n) — الزمن خطّي مع البيانات. الطريقة الثانية اسمها O(log n) — الزمن لوغاريتمي، بيكبر ببطء شديد.

التعريف العلمي

Big O بيوصف "أسوأ سيناريو" لزمن تنفيذ خوارزمية كدالة في حجم الدخل n، مع تجاهل الثوابت والعوامل الأقل أهمية. مثلاً:

• 3n + 5 = O(n) — بنشيل الـ 3 والـ 5
• 2n² + 100n = O(n²) — مع n الكبيرة، n² بيغطّي على كل حاجة
• log₂(n) أو log₁₀(n) = O(log n) — قاعدة اللوغاريتم مش مهمة

ليه نشيل الثوابت؟ لأن Big O بيقيس "النمو" لما n تكبر جداً. مع n=مليون، 2n² فيها 2 تريليون عملية، والـ 100n فيها 100 مليون. الـ 100 مليون مش هتبان جنب 2 تريليون، فبنشيلها.

أهم 5 درجات تعقيد لازم تحفظهم

• O(1) — ثابت. عملية واحدة مهما كبرت البيانات. مثال: قراءة أول عنصر في array، أو الوصول لمفتاح في dict.
• O(log n) — لوغاريتمي. مثال: البحث الثنائي في قائمة مرتبة. مع 10 مليون عنصر، 24 خطوة.
• O(n) — خطّي. مثال: المرور على كل عنصر في array. مع 10 مليون، 10 مليون عملية.
• O(n log n) — تقريباً خطّي. مثال: خوارزميات الترتيب الجيدة زي Merge Sort و Quick Sort.
• O(n²) — تربيعي. مثال: nested loops. مع 10000 عنصر، 100 مليون عملية. مع مليون، تريليون عملية.

كود حقيقي يقيس الفرق بنفسه

مش هنفهم Big O فعلاً غير لما نقيسه بإيدنا. الكود ده بـ Python 3.12 بيقارن بحث خطّي ببحث ثنائي على array فيها 10 مليون رقم:

import time

def search_linear(items, target):
    for item in items:
        if item == target:
            return True
    return False

def search_binary(sorted_items, target):
    low, high = 0, len(sorted_items) - 1
    while low <= high:
        mid = (low + high) // 2
        if sorted_items[mid] == target:
            return True
        elif sorted_items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return False

n = 10_000_000
data = list(range(n))
target = n - 1  # أصعب حالة: العنصر في الآخر

start = time.perf_counter()
search_linear(data, target)
print(f"Linear: {(time.perf_counter() - start)*1000:.2f} ms")

start = time.perf_counter()
search_binary(data, target)
print(f"Binary: {(time.perf_counter() - start)*1000:.3f} ms")

على لاب توب i7 جيل 12 المخرج بيكون:

Linear: 380.42 ms
Binary: 0.012 ms

الفرق ≈ 31,700 ضعف على نفس البيانات ونفس السيرفر. ده مش تحسين عشوائي — ده الفرق بين O(n) و O(log n).

الأرقام بتتكلم

بفرض إن الكمبيوتر بيعمل 100 مليون عملية في الثانية (تقدير معقول لكود Python حديث):

• O(n) على n=1,000,000 → 0.01 ثانية
• O(n log n) على n=1,000,000 → 0.2 ثانية
• O(n²) على n=1,000,000 → 10,000 ثانية ≈ 2.7 ساعة
• O(n²) على n=10,000,000 → 11.6 يوم

لو شفت function في الإنتاج بتاخد ساعات على بيانات صغيرة-متوسطة، 90% احتمال إنها O(n²) متخفّية في nested loop.

الـ trade-off اللي مش بيقولوه

كود O(n²) أبسط في الكتابة وأسهل في القراءة. كود O(log n) أو O(1) محتاج هيكل بيانات مرتب أو hash table، يعني تكلفة ذاكرة وإعداد إضافي.

الافتراض: لو بياناتك ≤ 1000 عنصر دايماً، nested loop O(n²) شغّال تمام (مليون عملية = أقل من 100ms). فوق كده، فكّر مرتين قبل ما تكتب loop داخل loop.

متى لا تستخدم Big O

Big O بيقيس "النمو مع n الكبير" بس. عنده 3 حدود لازم تعرفها:

• على بيانات صغيرة ثابتة (10–100 عنصر)، O(n²) ممكن تكون أسرع من O(n log n) بسبب الـ constant overhead.
• Big O ما بيقيسش استهلاك الذاكرة. ده موضوع تاني اسمه Space Complexity.
• Big O بيتجاهل الـ cache locality والـ branch prediction. كود O(n) على array بسيطة أسرع من O(n) على linked list حتى لو نفس الـ Big O.

الخطوة التالية

افتح آخر function كتبتها فيها loop. عُد الـ loops:

• loop واحدة → O(n)
• nested loop → O(n²)
• 3 loops متداخلة → O(n³) — وده غالباً غلط

جرّب الـ function على n=10,000 وقيس الزمن بـ time.perf_counter(). جرّبها تاني على n=20,000. لو الزمن اتضاعف، الكود O(n). لو الزمن طلع 4 أضعاف، الكود O(n²) — وعندك مشكلة هتظهر مع كبر البيانات.

المصادر

• Cormen, Leiserson, Rivest, Stein — "Introduction to Algorithms" (CLRS)، الإصدار الرابع، الفصل 3 "Characterizing Running Times".
• Big-O Cheat Sheet — مرجع سريع لتعقيد كل الخوارزميات الشائعة: bigocheatsheet.com
• Python time.perf_counter() documentation: docs.python.org/3/library/time.html
• Donald Knuth — "The Art of Computer Programming"، Volume 1، Section 1.2.11 "Asymptotic Representations".