تدوين Big-O هو المعيار الرياضي الذي يقيس أسوأ سيناريو لنمو وقت التنفيذ (Time Complexity) أو استهلاك الذاكرة (Space Complexity) في الخوارزمية مع تضخم حجم المدخلات (n). لا يقيس هذا المقياس الثواني الفعلية على جهاز بعينه، بل يصف سلوك الكود عند التوسع من مئة عنصر إلى مئة مليون عنصر.
لماذا لا يكفي قياس السرعة بساعة الإيقاف؟
قد يعمل كود غير فعال بسرعة مقبولة على حاسوب حديث عندما تكون البيانات صغيرة، لكنه يتوقف تماماً في بيئة الإنتاج. يساعدك تحليل Big-O على إهمال الثوابت الصغيرة والتركيز على الحد المهيمن الذي يحدد قابلية التوسع.
- تجاهل الثوابت: حلقتان منفصلتان بطول n تُحسبان O(n) وليس O(2n).
- أخذ الحد الأكبر: إذا احتوى الكود على O(n²) وO(n)، فإن التعقيد الكلي يُختصر إلى O(n²).
- التمييز بين الزمن والذاكرة: أحياناً نضحي بذاكرة إضافية (Space) عبر جداول التجزئة (Hash Maps) لتسريع الزمن (Time).
ترتيب مستويات التعقيد من الأسرع إلى الأبطأ
التدوينالاسم الشائععدد العمليات عند n = 1,000مثال خوارزميO(1)ثابت (Constant)1الوصول لعنصر في مصفوفة أو قاموسO(log n)لوغاريتمي (Logarithmic)~10البحث الثنائي (Binary Search)O(n)خطي (Linear)1,000البحث التسلسلي في قائمةO(n log n)خطي لوغاريتمي~10,000خوارزمية MergeSortO(n²)تربيعي (Quadratic)1,000,000حلقات متداخلة مثل Bubble SortO(2ⁿ)أسي (Exponential)رقم فلكيفيبوناتشي التكراري الساذج
قد يعجبك ايضا
مثال تطبيقي: تحويل حل O(n²) إلى O(n)
في مسألة البحث عن رقمين مجموعهما يساوي هدفاً محدداً، تستهلك الحلقات المتداخلة وقتاً تربيعياً، بينما يحلها القاموس بزمن خطي:
def two_sum_fast(nums: list[int], target: int) -> tuple[int, int] | None:
seen = {} # ذاكرة إضافية O(n) لتسريع الزمن إلى O(n)
for idx, num in enumerate(nums):
complement = target - num
if complement in seen:
return (seen[complement], idx)
seen[num] = idx
return None
تحسين الخوارزمية من O(n²) إلى O(n) يمنحك تفوقاً في الأداء لا يمكن لأي ترقية عتادية أن تعوضه عند التعامل مع البيانات الضخمة.
أسئلة شائعة
- السؤال: هل O(1) يعني دائماً أن الكود يستغرق نانو ثانية؟ الإجابة: لا، بل يعني أن زمن التنفيذ يظل ثابتاً مهما كبر حجم البيانات المدخلة.
- السؤال: ما الفرق بين Big-O وBig-Theta؟ الإجابة: يصف Big-O الحد الأعلى لأسوأ حالة، بينما يحدد Big-Theta النطاق الدقيق الضيق للأداء.
- السؤال: هل يمكن تجاهل التعقيد المكاني؟ الإجابة: في الخوادم السحابية والأنظمة المدمجة، قد يؤدي استهلاك الذاكرة المفرط إلى انهيار الخدمة (Out of Memory)، لذا لا بد من موازنته مع الزمن.
التعليقات (0)
أضف تعليقك