المستوى: مبتدئ
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 مليون عملية. مع مليون، تريليون عملية.
