كيف ينمو التكلفة

يقيس Big O كيف ينمو التكلفة مع نمو المدخلات. ليس معامل الثابت — بل المعدل. خوارزميتان تعملان كلتاهما في "بضعة ميلي ثانية" عند N=100 قد تتباعدان بعامل 10,000 عند N=10,000، إذا كانت إحداهما تعمل بزمن O(N) والأخرى بزمن O(N²).

فئات التعقيد الشائعة

O(1) — ثابت. نفس التكلفة بغض النظر عن N. أمثلة: البحث في جدول التجزئة باستخدام المفتاح، الوصول إلى عنصر في مصفوفة باستخدام الفهرس، الدفع/السحب في المكدس. مضاعفة N لا تغير شيئاً.

O(log N) — لوغاريتمي. كل خطوة تقلل العمل المتبقي إلى النصف. أمثلة: البحث الثنائي في مصفوفة مرتبة، استعلام BVH المكاني في محرك ألعاب، عمليات شجرة ثنائية متوازنة. عند N=1,000,000: log₂(1,000,000) ≈ 20 خطوة.

O(N) — خطي. التكلفة تزداد مع حجم المدخلات. أمثلة: المسح الخطي لقائمة، قراءة ملف، عد العناصر في مجموعة. عند N=10,000: 10,000 عملية.

O(N log N) — خطي لوغاريتمي. قريب من الخطي، لكنه أسوأ قليلاً. أمثلة: الترتيب بالدمج، خوارزميات أقصر مسار فعالة (ديكسترا باستخدام كومة). عند N=10,000: حوالي 133,000 عملية.

O(N²) — تربيعي. التكلفة تنفجر. أمثلة: استدعاء list.contains() داخل حلقة على نفس القائمة، ترتيب الفقاعات، المقارنة الساذجة لكل الأزواج. عند N=1,000: 1,000,000 عملية. عند N=10,000: 100,000,000 عملية.

O(2^N) — أسي. غير قابل للاستخدام على أي نطاق ذي معنى. أمثلة: الخوارزميات التوافقية بالقوة الغاشمة، إيجاد جميع المجموعات الفرعية. عند N=30: أكثر من 1,000,000,000 عملية.

المقياس الذي يجعله مرئيًا

مقارنات N=10:
O(N):   10
O(N²):  100
النسبة:  10x

N=1,000 مقارنة:
O(N):   1,000
O(N²):  1,000,000
النسبة:  1,000x

N=10,000 مقارنة:
O(N):   10,000
O(N²):  100,000,000
ratio:  10,000x

عندما تكون N=10، يكاد الفرق لا يُلاحظ. أما عندما تكون N=10,000، فإن الخوارزمية ذات التعقيد O(N²) تعمل أبطأ بمقدار 10,000 مرة. ولهذا السبب بقي MOAD-0001 غير مرئي لعقود: كانت الرسوم البيانية التي عمل عليها في 1993 تحتوي على 50 عقدة فقط. وبحلول 2020، كان الكود نفسه يعمل على رسوم بيانية للتبعيات تحتوي على 50,000 عقدة.

تصنيف ثلاث عمليات

طبّق فئات التعقيد على عمليات ملموسة. السؤال الأساسي لكل عملية: كم عدد العمليات المطلوبة مع زيادة N؟

كود صحيح، منحنى نمو خاطئ

كود صحيح يعمل بزمن O(N²) ينتج نتائج مطابقة لكود O(N). الاختبارات تمر. المخرجات تتطابق. لا يحدث أي استثناء. يختبئ العيب في منحنى النمو.

هذه الخاصية تجعل عيوب O(N²) رسوبية: تتصلب داخل كود يعمل ولا تصبح مرئية إلا عندما ينمو N بعد عتبة معينة. لم يتغير الكود. العالم من حوله تغير.

MOAD-0001: العيب الرسوبي

المثال الأكثر شيوعًا: visited = [] داخل حلقة اجتياز الرسم البياني.

visited = []
for node in graph:
if node not in visited:  # مسح O(N) في كل استدعاء
visited.append(node)
process(node)

كل استدعاء not in visited يفحص من 0 إلى len(visited)-1 عنصر. N استدعاء × N/2 عنصر مفحوص في المتوسط = O(N²) إجمالي. الحل: سطر واحد.

visited = set()  # اختبار عضوية O(1)
for node in graph:
if node not in visited:  # بحث تجزئة O(1)
visited.add(node)
process(node)

نفس السلوك. نفس المخرجات. نفس الاختبارات التي تمر. يتغير معدل النمو من O(N²) إلى O(N). عند N=1,000: أسرع بـ1,000 مرة. عند N=10,000: أسرع بـ10,000 مرة.

لماذا زرع عصر Hamming هذا

في Java وC المبكرة، كان ArrayList (المصفوفة الديناميكية) الحاوية التسلسلية الافتراضية. كانت المجموعات Sets موجودة لكنها لم تكن شائعة — فكان المطورون يلجؤون إلى ما يألفونه. كان اجتياز رسم بياني عام 1993 عند N=50 يعمل بسرعة ميكروثانية باستخدام visited = []. دخل هذا الكود إلى نظام التحكم بالإصدارات، وتم نسخه، وأُدرج في المكتبات، وشُحن عبر مديري الحزم. وبحلول 2020، كان نفس النمط يعمل على رسوم بيانية للتبعيات تحتوي على 50,000 عقدة.

كان الكود صحيحًا في 1993. أصبح مكلفًا عندما تغير العالم من حوله. زرع عصر Hamming هذا النوع من العيوب لأنه لم يطرح سؤال معدل النمو.

التشخيص والإصلاح

طبّق التشخيص: ابحث عن نمط O(N²)، وحدد الإصلاح.

ما تغييرات التسمية

قبل أن يكون لـ Big O اسم، لاحظ المبرمجون أن "هذا يعمل ببطء". قاموا بالتنميط. أعادوا الكتابة. لكنهم لم يستطيعوا تعليم النمط — كان بإمكانهم فقط الإشارة إلى الحالات. نمط بدون اسم لا يمكن أن ينتشر.

بعد أن أصبح لـ Big O اسم، استطاع مهندس كبير أن يقول "هذا O(N²)، استبدله بمجموعة" ويفهم المهندس الصغير، ويطبق، ويعلم النمط بدوره. الاسم جعل النمط وحدة معرفية قابلة للنقل.

كان Hamming يعرف هذه الديناميكية في مجالات أخرى. وصف كيف أتاحت تسمية "spaghetti code" في الستينيات للمجتمع التعرف على فئة من العيوب التي عاشها الجميع لكن لم يسمها أحد، ومناقشتها، وفي النهاية القضاء عليها. تنطبق الآلية نفسها على فئات التعقيد.

يضيف Unhamming المفردات التي أغفلها Hamming: O(1)، O(log N)، O(N)، O(N log N)، O(N²)، O(2^N). هذه الأسماء تتيح لك رؤية منحنى النمو في الكود الذي تقرأه، والتنبؤ بالأداء عند التوسع، والتواصل بدقة حول الإصلاحات. وهي تفي باختبار Hamming نفسه للأساسيات: دائمة، ومولدة لمعظم بقية المجال. [TITLE who_coined_big_o/]

من نظرية الأعداد إلى علوم الحاسب

لم تنشأ صيغة Big O في علوم الحاسب. بل نشأت في الرياضيات البحتة — وتحديداً في نظرية الأعداد — قبل 74 عاماً من أن يقوم دونالد كنوث بتكييفها للخوارزميات.

بول باخمان، 1894

قدّم عالم الرياضيات الألماني بول باخمان صيغة O في كتابه الصادر عام 1894 بعنوان Die Analytische Zahlentheorie (نظرية الأعداد التحليلية). كان بحاجة إلى طريقة مختصرة للتعبير عن أن كمية ما لا تنمو أسرع من كمية أخرى، حتى عامل ثابت. فكتابة 'f(n) = O(g(n))' تعني: f تنمو بسرعة لا تتجاوز سرعة g. وقد سمح ذلك لعلماء نظرية الأعداد بالتفكير في حدود الخطأ في التقريبات دون الحاجة إلى تتبع الثوابت الدقيقة.

لم يكن باخمان يفكر في الحلقات التكرارية أو هياكل البيانات أو زمن التنفيذ. كان يفكر في كيفية توزيع الأعداد الأولية — وتحديداً في حدود الخطأ في مبرهنة الأعداد الأولية.

إدموند لانداو، 1909

قام عالم الرياضيات الألماني إدموند لانداو بتعميم هذه الصيغة في كتابه الصادر عام 1909 بعنوان Handbuch der Lehre von der Verteilung der Primzahlen (دليل توزيع الأعداد الأولية). كما قدّم لانداو الصيغتين المرتبطتين o (ليتل-أو) واستخدم عائلة الرموز التقاربية على نطاق واسع حتى أصبحت هذه العائلة تُعرف باسم ترميز باخمان-لانداو أو ببساطة ترميز لانداو.

لمدة ستة عقود، بقيت صيغة O حصرياً في الرياضيات. ولم يفكر أي مبرمج بها.

دونالد كنوث، 1968 و1976

ترجم دونالد كنوث الترميز إلى علم الحاسوب. ففي كتابه فن برمجة الحاسوب (المجلد 1، 1968)، استخدم كنوث ترميز O لوصف زمن تشغيل الخوارزميات — وهو نقل مباشر لأداة باخمان إلى مجال جديد. وكان أول من طبقها بشكل منهجي في تحليل الخوارزميات.

في عام 1976، نشر كنوث ورقة قصيرة في SIGACT News بعنوان "Big Omicron and Big Omega and Big Theta". وقدّم فيها أوميغا (Ω) للحدود الدنيا وثيتا (Θ) للحدود الدقيقة، مكمّلاً بذلك المفردات الرمزية الثلاث التي يستخدمها علم الحاسوب اليوم. كما دعا إلى توحيد استخدام هذه الرموز عبر المجال — وهو عمل توحيدي متعمد سرّع من انتشارها.

بحلول أوائل الثمانينيات، ظهرت Big O في كل كتاب دراسي عن الخوارزميات. وبحلول التسعينيات، أصبحت مفردات قياسية في المقابلات.

رحلة استمرت 74 عامًا

1894 — باخمان يقدم O في نظرية الأعداد
1909 — لانداو يعمّم O وo وعائلة الترميز الكاملة
1953 — يبدأ هامينغ أبحاثه في مختبرات بيل (ولم يتعلم Big O كأداة في علوم الحاسب)
1968 — يطبّق كنوث O على تحليل الخوارزميات في المجلد الأول من TAOCP
1976 — يضيف كنوث أوميغا وثيتا؛ ويطالب بالتوحيد القياسي
1980s — تدخل Big O جميع مناهج علوم الحاسب
1993 — تتشكل طبقة الرواسب MOAD-0001 في كود الإنتاج
1995 — يدرّس هامينغ النسخة النهائية من مقرره؛ ولا يغطي Big O أبدًا
2026 — يُعثر على MOAD-0001 في أكثر من 1,000 مشروع مفتوح المصدر

قضى أداة باخمان 74 عامًا في الرياضيات البحتة، مرئية لكل رياضياتي لكن غير مرئية لكل مبرمج. رأى كنوث إمكانية نقلها. أما هامينغ — الذي عمل في نفس الحقبة وتعاون مع نفس مجتمع الحوسبة — فلم يدرجها في مقرره.

لماذا كان توحيد كنوث مهمًا

لم تكتفِ ورقة كنوث البحثية لعام 1976 بتقديم أوميغا وثيتا. بل جادلت بأن المجال بحاجة إلى تدوين موحد، وأن التدوين غير المتسق كان ضارًا فعليًا. استخدمت كتب دراسية مختلفة O لتعني أشياء مختلفة — أحيانًا كحد أعلى، وأحيانًا كتقريب، وأحيانًا دون تحديد ما إذا كانت الثوابت مهمة. قام كنوث بتنظيف هذا الالتباس.

هذا هو ديناميكية تسمية الأنماط عند هامينغ مطبقة على التدوين نفسه. قبل أن يوحد كنوث الرموز، لم يكن بإمكان المهندسين التواصل بدقة حول ادعاءات التعقيد عبر الكتب الدراسية أو الأوراق البحثية أو الفرق. بعد التوحيد، أصبحت عبارة "هذا يعمل في O(N log N)" تحمل معنى واحدًا بالضبط بغض النظر عن قائلها.

ساهم كنوث أيضًا بالترجمة غير الرسمية: "O(f(n)) تعني أن زمن التشغيل لا يتجاوز ثابتًا مضروبًا في f(n)، لكل n كبير بما يكفي." أصبح هذا التفسير — الحد الأعلى، حتى عامل ثابت، للمدخلات الكبيرة — الحدس القياسي الذي يتعلمه كل مبرمج.