آخر تحديث: 2026-06-23

معدل نمو Big-O

تُصنِّف علامة Big-O كيفية تطور متطلبات الخوارزمية من الموارد مع نمو حجم المدخلات. بدلاً من قياس الثواني على آلة بعينها، تلتقط شكل النمو — هل يتضاعف العمل حين يتضاعف n، أم يتربع؟ الفئات الست أدناه هي الأكثر مصادفةً في الكتب المقررة والمقابلات التقنية.

الفئات الست الشائعة

O(log n) — لوغاريتمية. كل خطوة تُلغي حصةً ثابتة من العمل المتبقي. البحث الثنائي في مصفوفة مرتبة من مليار عنصر لا يحتاج سوى 30 مقارنة لأنه يُنصِّف مساحة البحث في كل خطوة. تندرج هنا عمليات البحث في أشجار البحث الثنائية المتوازنة والتكرارات المستندة إلى "فرِّق تسُد".

O(n) — خطية. ينمو العمل بنسبة مباشرة مع حجم المدخلات. تمرير واحد عبر مصفوفة للعثور على أعلى قيمة، وعدُّ المحارف في سلسلة نصية، وقراءة كل عنصر في قائمة، كلها خطية. تُعدُّ الخوارزميات الخطية كفؤةً بوجه عام.

O(n log n) — خطية-لوغاريتمية. التعقيد الأكثر شيوعاً للفرز. يُحقق فرز الدمج وheapsort وTimsort (المستخدم في Python وJava) جميعها O(n log n)، وهو الحد النظري الأدنى للفرز القائم على المقارنة. عند $n = 10^6$، يبلغ العدد نحو عشرين مليون عملية — سريع في الواقع العملي.

O(n²) — تربيعية. حلقتان متداخلتان على المدخلات. فرز الفقاعة والإدراج والضرب الساذج للمصفوفات كلها O(n²) في أسوأ الأحوال. عند $n = 10^4$ يبلغ العدد مئة مليون عملية؛ وعند $n = 10^6$ يصبح تريليوناً — مستحيل التطبيق على البيانات الكبيرة.

O(2ⁿ) — أسية. يتضاعف العمل مع كل عنصر إضافي. تُعيد خوارزمية Fibonacci العودية الساذجة حساب المسائل الفرعية بشكل أسي؛ وكذلك تعداد جميع المجموعات الجزئية ينمو كـ $2^n$. عند n = 40 يتجاوز العدد تريليوناً.

O(n!) — مضروبية. أسرع فئة نمو في تحليل الخوارزميات اليومي. حلول القوة الغاشمة لمسائل التباديل — استعراض كل جولة ممكنة في مسألة البائع المتجول — تُنجز عملية واحدة لكل تبديل، وعدد التباديل هو $n!$. عند n = 20 يتجاوز العدد ألفَي كوينتيليون عملية.

مثال توضيحي عند n = 20

$\log_2 20 \approx 4.32 \quad\quad 20 \quad\quad 20 \log_2 20 \approx 86.4$

$20^2 = 400 \quad\quad 2^{20} = 1{,}048{,}576 \quad\quad 20! \approx 2.43 \times 10^{18}$

النسبة بين O(n log n) وO(n!) عند n = 20 تبلغ نحو $10^{16}$ — الفارق بين فرز سريع والانتظار مدةً أطول من عمر الكون.

إرشادات عملية

تؤثر الثوابت وسلوك الذاكرة المخبئية في n الصغير؛ التعقيد يهيمن في n الكبير. عند نحو n = 10,000 يبدأ O(n²) في إثارة الإشكاليات على العتاد الحديث (مع افتراض عمليات بسيطة). فوق $n = 10^6$ تُفرض الحاجة عموماً إلى خوارزمية من النوع O(n log n) أو أكفأ. الخوارزميات الأسية والمضروبية تستلزم أساليب التقريب والبرمجة الديناميكية وتشذيب الفضاء لأي مدخلات واقعية.

محوّل الأنظمة العددية مفيدة عند العمل مع التمثيلات الثنائية لفضاء المدخلات.