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 اسرع")
