في علوم الحاسوب، يُستخدم ترميز Big O notation لتحديد الحد الأعلى لأداء الخوارزمية. يُطبّق بشكل أساسي لتقدير الحد الأقصى للوقت الذي تستغرقه الخوارزمية كدالة لحجم المدخلات، ولكنه يمكن أن يُستخدم أيضًا لتحديد استهلاك الذاكرة. في هذا المقال، سنستعرض الأنواع الأكثر شيوعًا من ترميز Big O، مستعينين بأمثلة كعكات أعياد الميلاد لتوضيح المفاهيم. لنتخيل أننا نستضيف حفلًا، ونحتاج إلى تحديد عدد الكعكات الواجب خبزها بناءً على عدد الحضور.
O(1) – Constant Time (الوقت الثابت)
في مثال Constant Time، بغض النظر عن عدد الأشخاص الذين يحضرون حفل عيد الميلاد، فإنك تقوم بإعداد كعكة واحدة فقط. وبالتالي، يظل وقت إعداد الكعكة ثابتًا.
تجدر الإشارة إلى أن ترميز Big O notation لا يحدد المدة الفعلية لـ Constant Time (ربما يستغرق إعداد الكعكة ساعة واحدة، أو ربما أربع ساعات). إنه فقط يوضح أن الوقت المستغرق لا يزداد مع زيادة عدد الضيوف.
من الأمثلة الواقعية لعملية O(1) الوصول إلى عنصر في مصفوفة (array) باستخدام مؤشرها (index). فاسترجاع عنصر من مصفوفة تضم 10 عناصر لا يختلف سرعة عن استرجاع عنصر من مصفوفة تضم مليون عنصر.
O(log n) – Logarithmic Time (الوقت اللوغاريتمي)
في مثال Logarithmic Time، تُستخدم كعكات أعياد الميلاد كحافز لحث الضيوف على الحضور في الوقت المحدد. يحصل أول شخص يصل على كعكة كاملة لنفسه. ثم يتقاسم الشخصان التاليان كعكة واحدة. ثم يتقاسم الأربعة أشخاص التاليون كعكة واحدة، وهكذا. لذا، يتطلب حفل لشخص واحد كعكة واحدة. ويتطلب حفل لشخصين أو ثلاثة كعكتين. ويتطلب حفل لأربعة إلى سبعة أشخاص ثلاث كعكات، ويتطلب حفل لثمانية إلى خمسة عشر شخصًا أربع كعكات. بشكل عام، يتطلب حفل يضم n شخصًا log2(n) كعكة.
المثال الأكثر شيوعًا في العالم الحقيقي لعملية O(log n) هو البحث الثنائي (binary search) في مصفوفة مرتبة (ordered array). تقوم هذه الخوارزمية بالنظر إلى منتصف المصفوفة وتتحقق مما إذا كانت القيمة المطلوبة أقل أو أعلى من القيمة الموجودة في المنتصف. وبما أن القائمة مرتبة، فإنها تعرف عندها أي نصف من المصفوفة يحتوي على القيمة المستهدفة. ثم تكرر العملية مع ذلك النصف من المصفوفة. لذا، بالنسبة لمصفوفة تضم 16 عنصرًا، يقوم التكرار الأول بتضييق نطاق البحث إلى 8 عناصر، ثم 4، ثم 2، ثم 1، بحد أقصى 4 تكرارات إجمالاً، أو log2(16).
O(n) – Linear Time (الوقت الخطي)
في مثال Linear Time، يحصل كل ضيف على كعكته الخاصة. إذا حضر n شخصًا إلى الحفل، فأنت بحاجة إلى إعداد n كعكة. وبالتالي، فإن الوقت المستغرق يرتبط ارتباطًا مباشرًا بعدد الضيوف.
مرة أخرى، لا يحدد ترميز Big O notation المدة الفعلية للوقت (ربما يستغرق إعداد الكعكة ساعة واحدة، أو ربما أربع ساعات)، بل يوضح فقط أن الوقت يزداد خطيًا مع عدد الضيوف.
من الأمثلة الواقعية لعملية O(n) هو البحث البسيط (naive search) عن عنصر في مصفوفة (array). في مصفوفة تضم 10 عناصر، في أسوأ الأحوال، سيتعين عليك فحص جميع العناصر العشرة للعثور على العنصر المطلوب. ولكن بالنسبة لمصفوفة تضم مليون عنصر، قد تضطر إلى فحص جميع المليون عنصر. بالطبع، قد تجد الحل مبكرًا، لكن ترميز Big O notation يحدد الحد الأقصى للوقت الذي ستستغرقه الخوارزمية.
O(n^2) – Quadratic Time (الوقت التربيعي)
في مثال Quadratic Time، يحصل كل ضيف على كعكته الخاصة. بالإضافة إلى ذلك، تُكتب أسماء جميع الضيوف على كل كعكة باستخدام بعض كريمة التزيين اللذيذة. في هذه الحالة، يتطلب حفل لشخص واحد كعكة واحدة عليها اسم واحد. ويتطلب حفل لشخصين كعكتين، كلتاهما عليها اسمين (إجمالي 4 أسماء)، ويتطلب حفل لثلاثة أشخاص ثلاث كعكات، جميعها عليها ثلاثة أسماء، أي ما مجموعه 9 أسماء.
بشكل عام، يتطلب حفل يضم n شخصًا كتابة n*n اسمًا (يُعرف أيضًا بـ n squared، أو n مرفوعة للقوة 2)، لذا فإن سرعة إعداد الكعكات (وكتابة جميع الأسماء) ترتبط بمربع عدد الضيوف.
من الأمثلة الواقعية لعملية O(n^2) هو البحث البسيط عن التكرارات (duplicates) في مصفوفة (array). في هذا السيناريو، تقوم بالمرور عبر جميع العناصر في المصفوفة، ولكل من هذه العناصر، تمر عبر المصفوفة مرة أخرى لمعرفة ما إذا كانت هناك أي تطابقات. بالنسبة لمصفوفة تضم 10 عناصر، يحتوي التكرار الخارجي (outer loop) على 10 تكرارات، ولكل منها 10 تكرارات من التكرار الداخلي (inner loop)، ليصبح المجموع 100. وبالنسبة لمصفوفة تضم مليون عنصر، يصبح المجموع ألف مليار. هناك حالة أكثر عمومية لـ O(n^2)، حيث بدلاً من أن يكون الوقت مرتبطًا بـ n مرفوعة للقوة 2 (n^2)، فإنه يرتبط بـ n مرفوعة للقوة c (n^c). وهذا ما يُعرف عادةً بـ Polynomial Time (الوقت متعدد الحدود).
O(n!) – Factorial Time (الوقت العاملي)
في مثال Factorial Time، يشارك الضيوف في مسابقة البولينج (Pétanque)، ويأخذ الفائز الكعكة إلى المنزل. ومع ذلك، هناك مشكلة بسيطة، وهي أن اللاعب الذي يبدأ الدور الأول يكون في وضع غير مؤاتٍ. للمساعدة في تسوية الأمور، تُلعب العديد من الألعاب بحيث يتم تغطية كل تبديل (permutation) للضيوف ويحصل الجميع على فرصة للبدء أولاً. تُكتب جميع هذه التباديل على الكعكة، مرة أخرى باستخدام بعض كريمة التزيين اللذيذة. هذا يعني أن حفلًا يضم شخصين يتضمن لعبتين، حيث يتناوب كل ضيف على البدء أولاً. ويتضمن حفل يضم ثلاثة أشخاص 6 ألعاب (إذا تخيلنا أن الضيوف هم آنا، براين، وكريس، فإن التباديل هي ABC, ACB, BAC, BCA, CAB, CBA).
بشكل عام، يتطلب حفل يضم n شخصًا n!، أو n factorial (عاملي n) من الألعاب، لذا فإن سرعة إعداد الكعكة ترتبط بهذا. يُحسب n! بضرب جميع الأعداد الصحيحة من n نزولاً إلى واحد: “n * (n - 1) * (n - 2) * ... * 2 * 1“. لذا، بالنسبة لحفل يضم شخصين، يكون الناتج 2 * 1، أو 2. وبالنسبة لحفل يضم ثلاثة أشخاص، يكون الناتج 3 * 2 * 1، وهو 6. من الأمثلة الواقعية لعمليات O(n!) أي شيء يتطلب تحليل قائمة من التباديل، مثل مشكلة البائع المتجول (traveling salesman problem).
الخاتمة
نأمل أن تكون أمثلة كعكات أعياد الميلاد قد سهّلت استيعاب مفهوم ترميز Big O! الرسم البياني أدناه يُعد أيضًا وسيلة مساعدة جيدة للذاكرة، حيث يوضح السرعات النسبية للخوارزميات (إذا كان هناك خيار، فإنك دائمًا ما ترغب في اختيار الأسرع!)
هناك عدد لا بأس به من ترميزات Big O الأخرى، مثل O(n log n) و O(c^n)، ولكنها جميعًا تتبع نفس النمط. إذا كنت ترغب في معرفة المزيد عنها، يمكنك البحث عن مقالات متخصصة.
💡 الخلاصة التقنية
يُعد فهم ترميز Big O أمرًا حيويًا لأي مبرمج يسعى لكتابة أكواد فعالة وقابلة للتطوير. فهو لا يخبرنا بالوقت الفعلي الذي تستغرقه الخوارزمية، بل يوضح لنا كيف يتغير أداؤها مع نمو حجم المدخلات. اختيار الخوارزمية ذات الأداء الأفضل (مثل O(1) أو O(log n)) يمكن أن يحدث فرقًا هائلاً في سرعة وكفاءة التطبيقات، خاصة عند التعامل مع مجموعات بيانات كبيرة جدًا. لذا، فإن تحليل التعقيد الزمني والمكاني للخوارزميات باستخدام Big O هو مهارة أساسية لضمان جودة البرمجيات.