Big O ببساطة: ليه كودك بيطير على 100 عنصر ويتعلّق على مليون؟
المستوى: مبتدئ. المقال ده لأي حد بدأ يكتب كود وعايز يفهم ليه بعض الحلول بتنهار لما البيانات تكبر.
بعد ما تخلّص المقال ده هتعرف تبص على أي دالة وتحكم بسرعة: دي هتفضل سريعة لما الداتا تكبر، ولا هتتعلّق؟ ده معنى Big O بالظبط.
المشكلة باختصار
كودك اشتغل تمام على 100 صف في الاختبار. نزل الإنتاج على مليون صف، بقى بياخد دقايق. السيرفر مش هو المشكلة غالبًا. المشكلة إن عدد العمليات بيكبر أسرع من البيانات نفسها. Big O هو اللغة اللي بنوصف بيها الكبر ده.
الفكرة بمثال: دليل التليفونات
عندك دليل تليفونات فيه 1000 اسم مرتّبين أبجديًا، وعايز تلاقي اسم "منى".
الطريقة الأولى: تقلب صفحة صفحة من الأول. لو "منى" في الآخر، ممكن تقلب 1000 مرة. دي اسمها O(n): الشغل بيزيد بنفس نسبة عدد الأسماء.
الطريقة التانية: تفتح النص. لو "منى" بعد الصفحة دي، تلغي النص الأول كله وتفتح نص الباقي، وهكذا. كل خطوة بتقسم الباقي على 2. عشان توصل في 1000 اسم محتاج حوالي 10 خطوات بس. دي اسمها O(log n).
نفس المشكلة، وفرق ضخم في الشغل: 1000 مقابل 10. ده جوهر Big O.
المفهوم بدقة
Big O بيوصف أسوأ حالة لنمو عدد العمليات مع كبر حجم المدخلات n. بنهمل الثوابت والتفاصيل الصغيرة، ونركز على شكل النمو نفسه. الترتيب من الأسرع للأبطأ للحالات الشائعة:
- O(1) — زمن ثابت. الوصول لعنصر بالفهرس، أو البحث في dict و set. مش بيفرق مليون أو مليار.
- O(log n) — البحث الثنائي في بيانات مرتّبة. كل خطوة بتنصّ المشكلة.
- O(n) — تمر على كل عنصر مرة. البحث الخطي.
- O(n log n) — الترتيب الجيد (sort).
- O(n²) — حلقة جوه حلقة. بتنفجر بسرعة على الداتا الكبيرة.
الافتراض هنا إن اللي بيفرق مع البيانات الكبيرة هو شكل النمو، مش سرعة الجهاز. لو عندك قائمة فيها 1,000,000 عنصر: البحث الخطي O(n) ممكن يفحص المليون كلهم، والبحث الثنائي O(log n) بيخلص في حوالي 20 مقارنة. ده فرق بين مليون خطوة و20 خطوة.
مثال تشغّله بنفسك
الكود ده بيقارن البحث في list (خطي) بالبحث في set (زمن ثابت) على مليون رقم:
import timeit
n = 1_000_000
data_list = list(range(n))
data_set = set(data_list)
target = n - 1 # أسوأ حالة: آخر عنصر
# O(n): بيمر على القائمة لحد ما يلاقيه
t_list = timeit.timeit(lambda: target in data_list, number=100)
# O(1): بيوصله على طول عن طريق الهاش
t_set = timeit.timeit(lambda: target in data_set, number=100)
print(f"list O(n): {t_list:.4f}s")
print(f"set O(1): {t_set:.6f}s")
print(f"الفرق: {t_list / t_set:.0f}x اسرع")
على جهاز عادي هتلاقي البحث في الـ list بياخد وقت محسوس، والبحث في الـ set شبه لحظي. الفرق بيوصل لآلاف المرات، وبيكبر كل ما n تكبر. جرّبه بـ n = 10,000 وبعدين n = 1,000,000 وشوف الفرق بيتضاعف إزاي.
ولو البيانات مرتّبة؟ البحث الثنائي
لو القائمة مرتّبة، مش محتاج set. الوحدة bisect في بايثون بتعمل بحث ثنائي O(log n) جاهز:
import bisect
data = list(range(1_000_000)) # مرتّبة
i = bisect.bisect_left(data, 999_999)
print(data[i] == 999_999) # True في ~20 مقارنة بس
الصورة فوق بتوضّح الفكرة: قائمة 1000 عنصر، البحث الخطي لحد 1000 خطوة، والبحث الثنائي حوالي 10 خطوات.
الـ trade-off هنا
الـ set والـ dict بيدّوك بحث O(1)، بس بتكسب السرعة وتخسر حاجتين: بيستهلكوا ذاكرة أكتر من الـ list لأن الهاش محتاج مساحة زيادة، وبيضيّعوا الترتيب. البحث الثنائي O(log n) بيوفّر ذاكرة، بس شرطه إن البيانات تفضل مرتّبة، والترتيب نفسه بيكلّف O(n log n) مرة واحدة. يعني: لو بتبحث كتير، رتّب مرة وابحث ثنائي؛ لو بتبحث مرة واحدة بس، البحث الخطي أبسط وكفاية.
متى لا تشغّل بالك بالـ Big O
لو بياناتك صغيرة وثابتة — 50 أو 100 عنصر مثلًا — الفرق بين O(n) وO(log n) مش هيتحس أصلًا. هنا الوضوح أهم من التحسين، وتحسين خوارزمية على 100 عنصر مضيعة وقت. ركّز على Big O لما البيانات تكبر أو تزيد مع الوقت، أو لما تلاقي حلقة جوه حلقة (O(n²)) على داتا كبيرة.
الخطوة التالية
افتح أبطأ دالة عندك ودوّر على حلقة جوه حلقة، أو بحث بـ in على list كبيرة جوه لوب. لو لقيت واحدة، حوّل الـ list لـ set وقيس الفرق بـ timeit زي فوق. لو الزمن نزل بشكل واضح، يبقى المشكلة كانت في شكل النمو مش في السيرفر.
المصادر
- Big O notation — Wikipedia: en.wikipedia.org/wiki/Big_O_notation
- MIT OpenCourseWare 6.006 Introduction to Algorithms: ocw.mit.edu/courses/6-006
- Python — TimeComplexity (زمن العمليات للـ list وset وdict): wiki.python.org/moin/TimeComplexity
- timeit — توثيق بايثون الرسمي: docs.python.org/3/library/timeit.html
- bisect — توثيق بايثون الرسمي: docs.python.org/3/library/bisect.html