الخوارزميات للمحترفين ترميز Big-O في الخوارزميات

ترميز Big-O هو ترميز رياضي في الأساس يُستخدم لموازنة معدّلات تقارب الدوال، وسنستعرض في هذا المقال استخدامات هذا الترميز في تحليل الخوارزميات وتصنيفها كما يلي.

إذا كانت ‎n -> f(n)‎ وn -> g(n)‎ دالتين مُعرّفتين على الأعداد الطبيعية، فسنقول أنّ ‎f = O(g)‎ فقط إذا كانت ‎f(n)/g(n)‎ محصورة bounded عندما يؤول n إلى اللا نهاية. أي أن ‎f = O(g)‎ فقط إذا كان هناك ثابت A، بحيث يكون
 

‎f(n)/g(n) <= A‎

لكل n.

وفي الواقع فإن نطاق استخدام ترميز Big-O أوسع قليلاً في الرياضيات، لكن سنضيّقه في النطاق المُستخدَم في تحليل الخوارزميات للتبسيط، أي الدوال المُعرَّفة على الأعداد الطبيعية والتي ليست لها قيم صفرية أو جذور zero values عندما يؤول n إلى اللانهاية.

شرح

لنأخذ حالة هاتين الدالتين:
 

‎f(n) = 100n^2 + 10n + 1‎ 7

والدالة
 

‎g(n) = n^2‎

من الواضح تمامًا أنهما تؤولان إلى اللانهاية عندما يؤول n إلى اللانهاية. لكن قد لا يكفي أحيانًا أن نعرف النهاية limit، فقد نرغب أيضًا في معرفة السرعة التي تقترب بها الدوال من نهايتها، وهنا يأتي دور ترميز Big-O إذ يساعد على تصنيف الدوال بحسَب سرعة تقاربها.

فعندئذ نطبّق التعريف للتحقق ممّا إذا كانت ‎f = O(g)‎ حيث لدينا:

 ‎f(n)/g(n) = 100 + 10/n + 1/n^2‎

 وبما أن ‎10/n‎ يساوي القيمة 10 عندما يكون n=1 ويتناقص مع تزايد قيمة n، وبما أنّ ‎1/n^2‎ تساوي 1 عندما يساوي n القيمة 1 وهو أيضًا يتناقص مع تزايد قيمة n، فنحصل على المتراجحة

 f(n)/g(n) <= 100 +10 + 1 = 111

وقد تحقّق شرط التعريف هنا لأنّنا وجدنا حدًّا bound للتعبير
 

‎f(n)/g(n)‎‎ -

وهو 111-، ونكون بهذا قد أثبتنا أنّ‎f = O(g)‎‎، ونقول أنّ f هي Big-O لـ ‎n^2‎.

هذا يعني أنّ f تؤول إلى اللانهاية بنفس سرعة g تقريبًا. قد يبدو هذا غريبًا في البداية لأنّنا وجدنا أنّ f أكبر بـ 111 مرة من g، أو بعبارة أخرى، عندما تنمو g بمقدار 1، فإن f تنمو بمقدار 111 على أقصى حد. والحقيقة أنّ ترميز Big-O ليس دقيقًا في تصنيف سرعات تقارب الدوال، لهذا نَستخدم علاقة التكافؤ equivalence relationship في الرياضيات عندما نريد تقديرًا دقيقًا للسرعة.

لكن إن أردت تصنيف الخوارزميات إلى أصناف عامّة بحسب السرعات، فإنّ Big-O كافية، إذ لن نحتاج إلى التمييز بين دالتين تنمو إحداهما أسرع من الأخرى بعدد محدد من المرات، بل المهم هو التمييز بين الدوال التي تنمو لانهائيًا أسرع من بعضها البعض.

على سبيل المثال، في حالة
 

‎h(n) = n^2*log(n)‎

 نلاحظ أنّ ‎h(n)/g(n) = log(n)‎ تؤول إلى ما لانهاية عندما يؤول n إلى ما لا نهاية، لذا فإنّ h ليست من الصنف O (n ^ 2)‎‎، لأنّ h تنمو لانهائيًا أسرع من n ^ 2.

اقتباس

ملاحظة جانبية: إذا كانت ‎f = O(g)‎ و ‎g = O(h)‎؛ فسيكون ‎f = O(h)‎، فمثلًا في حالتنا هذه سيكون لدينا ‎f = O(n^3)‎ و ‎f = O(n^4)‎ …

وفي مجال تحليل تعقيد الخوارزميات، نكتب ‎f =‎ O(g)‎ للدلالة على أنّ:

f = O(g)‎‎ و ‎g = O(f)‎

 والتي يمكن تأويلها على أنّ g هي أصغر دالة من الصنف Big-O لــ f؛ أما في الرياضيات فنقول أنّ هاتين الدالتين Big-Theta لبعضها البعض.

كيفية الاستخدام

أول شيء عليك حسابه عند موازنة أداء الخوارزميات هو عدد العمليات التي تجريها الخوارزمية، وهو ما يُسمّى وقت التعقيد time complexity.

ونفترض في هذا النموذج أنّ كل عملية أساسية (الجمع والضرب والمقارنة والتعيين وما إلى ذلك) تستغرق مقدارًا ثابتًا من الوقت، ونحسب عدد هذه العمليات. ونعبر في الغالب عن هذا العدد كدالة لحجم الدخل -الذي نصطلح على تسميته n-، ويؤول هذا العدد (الدالة) في الغالب إلى ما لا نهاية عندما يؤول n إلى ما لا نهاية، أما خلاف ذلك، فنقول أنّ الخوارزمية من النوع O (1)‎‎.

ونحن نصنّف الخوارزميات إلى أصناف بحسب سرعات الدوال ونمثّلها بالترميز Big-O: فمثلًا إن قلنا أنّ خوارزميةً ما من النوع الآتي:

 O (n ^ 2)‎‎

 فإنّنا نقصد أنّ عدد العمليات التي تنفّذها الخوارزمية -معبَّرًا عنها كدالة لـ n- هو O (n ^ 2)‎‎. وهو ما يعني أنّ سرعة الخوارزمية تقارب سرعة خوارزمية تجري عددًا من العمليات يساوي مرّبع حجم الدخل أو أسرع. لاحظ لفظة أو أسرع، لقد وضعناها لأنّنا استخدمنا Big-O بدلاً عن Big-Theta، ذلك أنّه من الشائع أن ترى الناس تكتب Big-O، رغم أنّهم يعنون Big-Theta.

ونحن نأخذ الحالة الأسوأ في حسابنا عادة عند عدّ العمليات، فإن كانت حلقة تكرارية تُنفَّذ n مرّةً على الأكثر وكانت تحتوي على 5 عمليات، فإنّ عدد العمليات المُقدَّر سيكون 5n. كذلك من الممكن مراعاة متوسط تعقيد الحالة.

اقتباس

ملاحظة سريعة: الخوارزمية السريعة هي تلك التي تنفذ عمليات قليلة، فكلما اقترب عدد العمليات المُنفّذة إلى اللانهاية بسرعة أكبر كانت الخوارزمية أبطأ، مثلًا: O (n)‎‎ أسرع من O (n ^ 2)‎‎ لأنّ الدالة n تؤول إلى اللانهاية أبطأ من n^2.

يمكن أن نأخذ مساحة التخزين بالحسبان كذلك، وهو ما يُسمّى تعقيد المساحة space complexity للخوارزمية، ذلك أن الوقت ليس المورد الوحيد المهم، وفي هذه الحالة نحسُب عدد البايتات التي تشغلها الخوارزمية في الذاكرة كدالة لحجم الدخل، ونستخدم Big-O كما في حالة تعقيد الوقت.

مثال عن حلقة بسيطة Simple Loop

الدالة التالية تبحث عن أكبر عنصر في المصفوفة:

int find_max(const int *array, size_t len) {
   int max = INT_MIN;
     for (size_t i = 0; i < len; i++) {
        if (max < array[i]) {
            max = array[i];
        }
    }
    return max;
}

حجم الدخل هو حجم المصفوفة، والذي سمّيناه ‎len‎ في الشيفرة أعلاه. دعنا الآن نَعُد العمليات.

int max = INT_MIN;
size_t i = 0;

تُنفَّذ هاتان العمليتان مرةً واحدة، لذا فلدينا عمليتان هنا. والآن نعدّ عمليات الحلقة:

if (max < array[i])
i++;
max = array[i]

لمّا كانت هناك 3 عمليات في الحلقة، وكانت الحلقة تُنفَّذ n مرة، فسنضيف ‎3n‎ إلى 2 (العمليتان اللتان حسبناهما من قبل)، ليبلغ الإجمالي ‎3n + 2‎.

تجري دالتنا إذن عددًا من العمليات مقداره ‎3n + 2‎ عملية للعثور على أكبر عنصر في المصفوفة (تعقيدها يساوي ‎3n + 2‎). وهذا يعرف بتعددية الحدود polynomial، وأسرع عواملها نموّا هو العامل n، لذا يساوي تعقيدها O (n)‎‎.

لعلّك لاحظت أنّ طريقة عدّ العمليات ليست دقيقة، فقد قلنا مثلًا أنّ  (max < array)‎ هي عملية واحدة، ولكن اعتمادًا على هندسة الحاسوب فقد تنطوي هذه العبارة على تعليمتين مثلاً، الأولى لقراءة الذاكرة والثانية للمقارنة. وقد اعتبرنا كذلك أنّ جميع العمليات متشابهة رغم أنّ العمليات التي تخصّ الذاكرة على سبيل المثال تكون أبطأ من العمليات الأخرى، كما يختلف أداؤها اختلافًا كبيرًا بسبب تأثيرات التخزين المؤقت cache.

كذلك تجاهلنا أيضًا تعليمة الإعادة return وحقيقةَ إنشاء إطار frame خاص بالدالة، وما إلى ذلك من الأمور الجانبية. لكنّ هذا لن يؤثّر في النهاية على تحليل التعقيد، ذلك أنّه مهما كانت طريقة عدّ العمليات، فلن يؤثّر إلا على معامل العامل n وكذلك لن يؤثر على الثابت، لذا ستظل النتيجة O (n)‎‎. ويُظهر التعقيد كيف تتطوّر الخوارزمية مع تطوّر حجم الدخل، بيْد أنّها ليست الجانب الوحيد الذي يمثّل الأداء.

مثال عن الحلقات المتشعبة Nested Loops

تتحقق الدالة التالية ممّا إذا كانت المصفوفة تحتوي أيّ تكرارات، وذلك عبر المرور على كل عنصر على حدة، ثم المرور مجدّدا على المصفوفة للتحقّق ممّا إذا كان هناك عنصر آخر يساويه.

_Bool contains_duplicates(const int *array, size_t len) {
   for (int i = 0; i < len - 1; i++) {
       for (int j = 0; j < len; j++) {
           if (i != j && array[i] == array[j]) {
               return 1;
           }
       }
   }
   return 0;
}

تنفّذ الحلقة الداخلية عند كل تكرار عددًا ثابتًا من العمليات (بغضّ النظر عن قيمة ‎n‎)، كما تنفّذ الحلقة الخارجية أيضًا بعض العمليات الثابتة علاوة على تنفيذ الحلقة الداخلية عدد ‎n‎ مرّة.

أيضًا، تنفَّذ الحلقةُ الخارجية نفسها ‎n‎ مرّة، وعليه تُنفّذ العمليات داخل الحلقة الداخلية ‎n^2‎ مرّة بينما تُنفّذ عمليات الحلقة الخارجية ‎n‎ مرّة، أمّا عملية التعيين إلى ‎i‎ فتُتفّذ مرّة واحدة. وهكذا يمكن التعبير عن التعقيد بمعادلة مثل ‎an^2 + bn + c‎، ولمّا كان المعامل الأعلى هو ‎n^2‎، فإنّ ترميز O سيساوي ‎O(n^2)‎.

لعلك لاحظت أن هناك فرصة لتحسين الخوارزمية أكثر، إذ يمكن مثلًا تجنّب إجراء نفس المقارنات أكثرة من مرّة. يمكننا أن نبدأ من ‎i + 1‎ في الحلقة الداخلية نظرًا لأنّ جميع العناصر التي تسبقه قد تم التحقق منها سلفًا وقورنت مع جميع عناصر المصفوفة، بما في ذلك العنصر الموجود عند الفهرس ‎i + 1‎. هذا يسمح لنا بحذف الاختبار ‎i == j‎.

_Bool faster_contains_duplicates(const int *array, size_t len) {
   for (int i = 0; i < len - 1; i++) {
       for (int j = i + 1; j < len; j++) {
           if (array[i] == array[j]) {
               return 1;
           }
       }
   }
   return 0;
}

كما ترى فإنّ هذا الإصدار أفضل لأنّه يُجري عمليات أقل، لكن كيف نترجم هذا في ترميز Big-O؟ حسنًا، في الإصدار الجديد، يُنفّذ مَتن الحلقة الداخلية المرات

 ‎1 + 2 + ... + n - 1 = n(n-1)/2‎

لا يزال هذا التعبير كثير الحدود من الدرجة الثانية، لذا سيظلّ التعقيد مساويا لـ ‎O(n^2)‎.

وقد قلّلنا التعقيد إذ خفّضنا عدد العمليات إلى النصف تقريبًا، بيْد أنّنا ما زلنا في نفس صنف التعقيد من Big-O. ونحتاج إلى تقسيم عدد العمليات على مقدار يؤول إلى اللا نهاية مع ‎n‎ من أجل تقليل التعقيد إلى صنف أدنى.

الخوارزميات اللوغاريتمية‎‎‎‎

لنفترض أنّ لدينا مشكلة ذات حجم n، ولنفترض أنّ حجم مشكلتنا الأصلية ينخفض إلى النصف (n / 2) بعد كل خطوة من خطوات الخوارزمية. أي أنّه في كل خطوة جديدة يصير حجم المشكلة نصف ما كانت عليه في الخطوة التي قبلها:

تكون المشكلة محلولة حين يتعذر تقليل حجمها أكثر بعد الخروج من شرط التحقق، أي عندما تكون n مساوية للقيمة 1.

لنفترض الآن أنّ حجم المشكلة يساوي n، نريد أن نحسب عدد الخطوات اللازمة لحل الخوارزمية، سنرمز لهذا العدد بالحرف k:

1. عند الخطوة k، سيساوي حجم المشكلة 1 (أي أنّ المشكلة ستكون قد حُلَّت).
2. من جهة أخرى، نعلم أنّه عند الخطوة k، ينبغي أن يساوي حجم المشكلة العدد (n/2^k).
3. من 1، 2، إذًا n = 2k.
4. طبّق دالة اللوغاريتم على كلا الجانبين:

log n = k * loge_2  →   k = loge n / loge 2

5. باستخدام المعادلة التالية:

logx (m) / logx (n) = logn (m)‎

حيث يرمز التعبير logt‎‎ إلى اللوغاريتم ذي الأساس t، وتصبح النتيجة k = log2 (n)‎‎ أو k = log n ببساطة.

اقتباس

نعلم الآن أنّ خوارزميتنا يمكن أن تُنفّذ log n على أقصى حدّ، وعليه يساوي تعقيد الوقت O (log n)‎‎

انظر المثال التوضيحي التالي:

for(int i=1; i<=n; i=i*2)
{
 // إجراء بعض العمليات
}

إن كان n يساوي 256، فكم تتوقّع أن يكون عدد الخطوات التي ستنفّذها الحلقة أو أي خوارزمية أخرى ينخفض حجم مشكلتها إلى النصف بعد كل خطوة؟

سنرمز للعدد الذي نبحث عنه بالرمز k، ونحسبه على النحو الآتي:

• k = log2 (256)‎‎.
• k = log2 (2^8)‎‎ ( نعلم أنّ log(a^a) = 1‎ لكل عدد a‎).
• k = 8.

هذا مثال آخر لتوضيح هذا النوع من الخوارزميات. وهي خوارزمية البحث الثنائي Binary Search Algorithm.

int bSearch(int arr[],int size,int item){
int low=0;
int high=size-1;
while(low<=high){               
    mid=low+(high-low)/2;               
    if(arr[mid]==item)                       
        return mid;               
    else if(arr[mid]<item)                       
        low=mid+1;               
    else  high=mid-1;     
    } 
 return –1;// لا يوجد
}

مثال على خوارزمية من الصنف O (log n)‎‎

انظر المشكلة التالية:

L قائمة مرتّبة تحتوي n عددًا صحيحًا نسبيًا (n كبيرة جدا)، على سبيل المثال ‎[-5, -2, -1, 0، 1، 2، 4]‎‎ (هنا، n تساوي 7). إذا كانت ‎L‎ تحتوي العدد الصحيح 0، فكيف يمكنك العثور على فهرس 0؟

المقاربة البسيطة

أول ما يتبادر إلى الذهن هو قراءة كل فهرس إلى حين العثور على 0، وفي أسوأ الحالات سيكون علينا إجراء ‎n‎ عملية، وعليه فإنّ التعقيد سيساوي O (n)‎‎.

لا مشكلة في هذا مع القيم الصغيرة لـ ‎n‎، ولكن هل هناك طريقة أفضل؟

مبدأ الحصار Dichotomy

انظر الخوارزمية التالية Python3:

a = 0
b = n-1
while True:
 h = (a+b) // (*)
 if L[h] == 0:
   return h
 elif L[h] > 0:
   b = h
 elif L[h] < 0:
   a = h

اقتباس

(*) تمثل // عملية القسمة الصحيحة integer division، لذا ستكون h عددًا صحيحًا. يحصركل من a و b فهرس العدد 0، فلا بدّ لفهرس 0 أن يكون محصورًا بينهما، وكل مرة ندخل إلى الحلقة، نختار فهرسًا بين aو‎b‎ ونستخدمه لتضييق المنطقة المراد البحث عنها.

وفي أسوأ الحالات، علينا الانتظار حتى يتساوى ‎a‎ و‎b‎، لكن كم عدد العمليات التي يتطلبها ذلك؟ قطعًا ليس n لأننا نقسم المسافة بين ‎a‎ و‎b‎ على 2 في كل مرة ندخل إلى الحلقة، لذا فالتعقيد يساوي O (log n)‎‎.

اقتباس

تنبيه: حين نكتب log فإننا نشير إلى اللوغاريتم الثنائي binary logarithm أو اللوغاريتم ذي الأساس 2، والذي يُكتب عادةً log_2 أو log2، لذا فإنّ O (log_2 n)‎‎ و O (log)‎‎ متكافئتان.

إذا صادفت خوارزمية يُقسم حجمها على عدد معيّن (2 أو 3 أو أيّ عدد) بعد كل خطوة، فإنّ تعقيدها سيكون لوغاريتميًا.

ترجمة -بتصرّف- للفصل الثالث من كتاب Algorithms Notes for Professionals.

اقرأ أيضًا

• المقالة السابقة: تعقيد الخوارزميات
• مدخل إلى الخوارزميات
• دليل شامل عن تحليل تعقيد الخوارزمية
• مدخل إلى الذكاء الاصطناعي وتعلم الآلة