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

لو كودك بيشتغل تمام على 100 عنصر وبيتعلق ساعة كاملة على 100 ألف عنصر، المشكلة مش في السيرفر ومش في اللغة. المشكلة في حاجة اسمها Big O Notation. ولو فهمتها صح، هتعرف من غير ما تشغّل الكود إذا كان هيقعد ثانية ولا يوم كامل.

المقال ده هيشرحلك Big O من الصفر. هتطلع بفهم عملي تقدر تستخدمه في الـ code review بكرة الصبح، مش مجرد كلام نظري في الجامعة.

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

لما بتكتب كود وبتجرّبه على بيانات صغيرة، كل حاجة بتبان حلوة. بس البيانات الحقيقية بتبدأ صغيرة وبتكبر. المستخدمين بيزيدوا، الجدول في قاعدة البيانات بيوصل لمليون صف، الـ API بتاعتك بتدخلها 10 آلاف طلب في الدقيقة بدل 100.

اللي بيحصل فعلاً إن في فرق هائل بين كود بياخد وقت ثابت وكود بياخد وقت بيتضاعف مع البيانات. وده اللي Big O بيقيسه.

مثال بسيط جداً: تدوّر على رقم تليفون صاحبك

تخيّل إن عندك دفتر تليفونات ورقي فيه 1000 اسم، عايز تلاقي رقم صاحبك "أحمد".

الطريقة الأولى: تفتح الدفتر من أوله وتبص اسم اسم لحد ما تلاقيه. لو "أحمد" في أول الدفتر، هتلاقيه بسرعة. لو في آخره، هتقرا 1000 اسم. ده اسمه Linear Search.

الطريقة الثانية: الدفتر مرتب أبجديًا. تفتحه في النص. لو الصفحة فيها حرف "ر"، يبقى "أحمد" في النصف الأول. تتجاهل النصف التاني كله وتفتح في نص النص الأول. وهكذا. بعد 10 خطوات تقريبًا تكون لقيته. ده اسمه Binary Search.

بالظبط ده الفرق اللي Big O بيوصفه. الطريقة الأولى لو الدفتر كبر لمليون اسم، ممكن تقرا مليون اسم. الطريقة التانية لو الدفتر كبر لمليون اسم، بتقرا 20 اسم بس. الفرق بين عمر كامل وكوبايتين شاي.

تعريف Big O بطريقة علمية ودقيقة

Big O Notation هي طريقة رياضية لوصف كيف يتغيّر زمن تنفيذ الخوارزمية مع زيادة حجم المدخلات. بمعنى أدق: هي تصف الحد الأعلى (upper bound) لمعدل النمو في أسوأ حالة.

بنكتبها بصيغة O(f(n)) حيث:

• n = حجم المدخلات (عدد العناصر، طول النص، عدد الصفوف).
• f(n) = الدالة اللي بتوصف معدل النمو.

المهم إن Big O بتتجاهل الثوابت والعوامل الصغيرة. خوارزمية بتاخد 3n + 5 ثانية، Big O بتاعتها O(n). ليه؟ لأن لما n بتكبر جدًا، الـ 3 والـ 5 بيبقوا تافهين.

أشهر 6 درجات تعقيد لازم تعرفهم

دي القايمة مرتبة من الأسرع للأبطأ. احفظها كأنها جدول الضرب:

1. O(1) — زمن ثابت: الكود بياخد نفس الوقت بغض النظر عن حجم البيانات. مثال: قراءة عنصر من Array بالـ index.
2. O(log n) — زمن لوغاريتمي: الزمن بيزيد ببطء جدًا حتى مع بيانات ضخمة. مثال: Binary Search.
3. O(n) — زمن خطي: الزمن بيزيد بنفس نسبة زيادة البيانات. مثال: Loop واحدة على Array.
4. O(n log n) — أفضل ما يمكن للترتيب: أسرع خوارزميات الترتيب الشائعة. مثال: Merge Sort, Quick Sort.
5. O(n²) — تربيعي: Loop جوّا Loop. لو البيانات اتضاعفت، الزمن يتضرب في 4. مثال: Bubble Sort.
6. O(2ⁿ) — أُسّي: كارثة. كل عنصر زيادة بيضاعف الزمن. مثال: Recursive Fibonacci بدون memoization.

كود Python شغّال يخليك تشوف الفرق بنفسك

السكربت ده بيقارن Linear Search و Binary Search على نفس البيانات. شغّله على جهازك وشوف الأرقام:

import time
import random

def linear_search(arr, target):
    for i, value in enumerate(arr):
        if value == target:
            return i
    return -1

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

# نختبر على مليون رقم مرتب
n = 1_000_000
data = list(range(n))
target = n - 1  # أسوأ حالة: العنصر في الآخر

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

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

النتيجة الفعلية على لاب توب عادي (Intel i5، 16GB RAM):

• Linear Search: حوالي 52 ميلي ثانية.
• Binary Search: حوالي 0.004 ميلي ثانية.

الفرق 13,000 ضعف تقريبًا على نفس البيانات بالظبط. ده مش تحسين بسيط، ده فرق بين تطبيق شغال وتطبيق ميت.

مثال تاني: ليه Loop جوّا Loop خطر؟

الكود ده بيدوّر على أزواج مكررة في List. شكله بريء، بس Big O بتاعته O(n²):

def find_duplicates_slow(arr):
    duplicates = []
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] == arr[j]:
                duplicates.append(arr[i])
    return duplicates

على 1000 عنصر: حوالي 50 ميلي ثانية. على 10,000 عنصر: حوالي 5 ثواني. على 100,000 عنصر: أكتر من 8 دقايق. لاحظ إن البيانات اتضاعفت 100 مرة، بس الزمن اتضاعف 10,000 مرة.

الحل بـ O(n) باستخدام Set:

def find_duplicates_fast(arr):
    seen = set()
    duplicates = []
    for value in arr:
        if value in seen:
            duplicates.append(value)
        else:
            seen.add(value)
    return duplicates

على 100,000 عنصر: أقل من 30 ميلي ثانية. الفرق هنا مش 10x ولا 100x. الفرق إن إصدار O(n) بيخلّص قبل ما إصدار O(n²) يبدأ يفكر.

إزاي تحسب Big O لكود قدامك في 30 ثانية

القواعد العملية اللي بتنفع 90% من الحالات:

1. Loop واحدة على المدخلات = O(n).
2. Loop جوّا Loop على نفس المدخلات = O(n²).
3. كل خطوة بتقسم البيانات على 2 = O(log n).
4. قراءة من Hash Map / Dictionary = O(1) في المتوسط.
5. استدعاء دالة بتنادي نفسها = شوف عدد الاستدعاءات وحجم كل واحد.

الـ Trade-offs اللي محدش بيقولهالك

Big O مش كل حاجة. في حاجات مهمة لازم تنتبه ليها:

• الذاكرة مقابل السرعة: اللي عملناه فوق بـ Set (الـ O(n)) بياخد ذاكرة إضافية بحجم البيانات. لو بياناتك 10GB، ممكن متلاقيش الذاكرة الكافية. التكلفة هنا: ذاكرة. المكسب: سرعة.
• الثوابت المخفية: O(n) بمعامل ثابت كبير ممكن يكون أبطأ من O(n²) على بيانات صغيرة. مثلًا، 10000n أبطأ من n² لما n < 10000.
• أسوأ حالة مقابل المتوسط: Quick Sort في المتوسط O(n log n)، بس في أسوأ حالة O(n²). لو بياناتك ممكن تيجي مرتبة بالعكس، اختار Merge Sort.

متى لا تشغل بالك بـ Big O

الافتراض إن عندك بيانات هتكبر. لو الكود ده هيشتغل مرة واحدة على 50 عنصر بس، متضيّعش وقتك في تحسين Big O. اكتب أبسط كود يقرأه أي حد في الفريق وامشي.

القاعدة: لو n < 1000 ومش هيكبر، التحسين الزائد ضرر مش مكسب. الكود الأبسط بيتقرأ أسرع، بيتصلّح أسرع، وبيغلط أقل. Big O مهم لما البيانات بتكبر بشكل غير متوقع، أو لما الكود بيشتغل ملايين المرات في اليوم.

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

افتح آخر Pull Request شغلت عليه، ودوّر على أي for جوّا for. لو لقيت واحد بيشتغل على Array مدخلات، اسأل نفسك: ممكن أحوّله لـ O(n) بـ Hash Map؟ لو الإجابة نعم وعدد العناصر ممكن يعدي الـ 10,000 مرة في الإنتاج، اعمل التغيير ده النهارده. لو متأكد إن الـ Array مش هيكبر، سيبه واتركز في حاجة أهم.

المصادر

• MDN Web Docs — Algorithm Glossary
• Wikipedia — Big O Notation
• Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms (CLRS)، الفصل 3: Growth of Functions.
• Gayle Laakmann McDowell — Cracking the Coding Interview، الفصل 6: Big O.
• Big-O Cheat Sheet — مرجع سريع لتعقيد الخوارزميات الشائعة
• Python timeit Documentation — لقياس زمن تنفيذ الكود