مستوى المقال: مبتدئ
Big O Notation للمبتدئ: ليه كودك بطيء لما البيانات بتكبر
لو الدالة بتاعتك بترد في 12 مللي ثانية على 100 صف وبتاخد 47 ثانية على 100,000 صف، السيرفر مش ضعيف. الفرق إن الخوارزمية بتكبر بسرعة أعلى من البيانات نفسها. Big O بيدّيك لغة بسيطة تقيس بيها ده قبل ما الكود يوصل للإنتاج.
المشكلة باختصار
أكتر من 60% من مشاكل الـ performance في تطبيقات الويب اللي شفناها مش في الـ DB ولا الـ network. هي خوارزمية O(n²) شغّالة على array بـ 5,000 عنصر بدل O(n log n) أو O(n). الفرق بين الاتنين على نفس البيانات ممكن يكون 800 ضعف زمن استجابة، وإنت قاعد تحاول تشتري سيرفر أكبر.
مثال للمبتدئ: دفتر التليفونات
تخيل عندك دفتر فيه 1,000 اسم مرتّب أبجدياً، وعايز تلاقي رقم "محمد عبد الله".
- الطريقة الأولى: تفتح صفحة صفحة من الأول لحد ما توصل للاسم. متوسط 500 محاولة. ده اللي بنسميه O(n).
- الطريقة الثانية: تفتح الدفتر في النص، تشوف الاسم اللي قدامك، تروح يمين أو شمال بناءً على الترتيب الأبجدي، وتقسّم النص تاني. أقصى 10 محاولات. ده اللي بنسميه O(log n).
على 1,000 اسم الفرق 50 ضعف. على مليون اسم الفرق 50,000 ضعف. ده اللي بيخلّي الكود نفسه شغّال أو بايظ لما البيانات تكبر، حتى لو محدش غيّر سطر واحد فيه.
تعريف Big O علمياً
دلوقتي بعد ما المثال واضح، نقدر نشيل الطبقة الإنشائية ونقول التعريف الدقيق. Big O بيوصف الحد الأعلى لمعدل نمو الزمن (أو الذاكرة) لدالة بالنسبة لحجم المدخل n. التعريف الرسمي من كتاب CLRS (Cormen 2009): دالة f(n) هي O(g(n)) لو في ثابت c و n₀ بحيث f(n) ≤ c·g(n) لكل n ≥ n₀.
الترجمة بالعربي العملية: مش بنحسب الزمن الفعلي بالمللي ثانية، بنوصف سلوك الزمن لما n يكبر جداً. الثوابت الصغيرة بتختفي، الحدود الأقل أهمية بتنسى. الهدف يدّيك مقياس سريع تقارن بيه خوارزميتين بدون ما تشغّلهم.
الـ 6 أنماط اللي هتقابلهم فعلاً
1. O(1) — زمن ثابت
الزمن نفسه بغض النظر عن حجم البيانات. مثل قراءة قيمة من dictionary أو الوصول لـ array index.
def get_user(users, user_id):
return users[user_id] # O(1)
2. O(log n) — لوغاريتمي
كل خطوة بتقسم البيانات نصين. Binary search على array مرتّب، أو فحص عقدة في شجرة متوازنة.
