تحليل الخوارزميات

هناك الكثير من الأمور المهمة التي يجب الاعتناء بها عند كتابة الخوارزميات منها الأمان وسهولة الاستخدام والقدرة على التطوير وغيرها، ولكنّ الأهم من كلّ ذلك هو أداء الخوارزمية؛ والسبب في ذلك هو أنّ جميع الأمور آنفة الذكر هي نتيجة حتمية لأداء الخوارزمية، ويمكن القول أنّ الأداء هو العملة التي يمكن استخدامها لشراء جميع الأمور السابقة.

إلى جانب ذلك فإن الأداء الجيّد يعني السرعة العالية والقابلية على التوسع؛ فما الفائدة مثلًا من محرّر نصوص قادر على تحميل 1000 صفحة ولكنّ تصحيح الأخطاء اللغوية فيه يتطلب دقيقة لكل صفحة، أو أنّ محرّر الصور يستغرق ساعة كاملة لتدوير صورة 90 درجة إلى اليسار.

كيف يمكن إذن مقارنة أداء خوارزميتين مختلفتين في أداء مهمّة معينة؟

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

1. يحتمل أنّ الخوارزمية الأولى ستؤدّي أداءً أفضل من الثانية عند استخدام بعض المدخلات، وأنّ الخوارزمية الثانية ستؤدّي أداءً أفضل من الأولى عند استخدام نوع آخر من المدخلات.
2. ويحتمل كذلك أنّ الخوارزمية الأولى ستؤدّي أداءً أفضل من الثانية عند استخدام بعض المدخلات على جهاز معيّن، وأنّ الثانية ستؤدي أداءً أفضل من الأولى عند استخدام بعض المدخلات على جهاز آخر.

التحليل المقارب

يتغلّب التحليل المقارب Asymptotic Analysis على المشاكل السابقة عن طريق تحليل الخوارزمية بالاعتماد على حجم المدخلات فقط (ولا يجري قياس الوقت الحقيقي لعمل الخوارزمية)، بمعنى أنّ التحليل المقارب يحسب مقدار الزيادة التي تطرأ على الوقت أو المساحة المشغولة من الذاكرة من قبل الخوارزمية عند زيادة المدخلات.

إنّ المقصود بالتعقيد الزمني للخوارزمية هو إجراء تحليل لعمل تلك الخوارزمية عند تغذيتها بمجموعة كبيرة جدًّا من المدخلات.

لنأخذ مسألة البحث عن عنصر معين في مصفوفة مرتّبة كمثال. يمكن إجراء عملية البحث بطرق متعددة، منها الطريقة الخطية (معدّل النمو فيها خطي) والطريقة الثنائية (معدّل النمو فيها لوغارتمي). ولنفترض أنّ عملية البحث الخطي أجريت في حاسوب سريع وأنّ عملية البحث الثنائي أجريت في حاسوب آخر بطي.

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

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

إلى جانب أنّ من الممكن أن لا يتعامل برنامج معين مع عدد كبير من المدخلات وبهذا ستؤدي الخوارزمية التي تصبح بطيئة جدًّا مع المدخلات الكثيرة أداءً أفضل في هذه الحالة الخاصة، وهذا ما لا يستطيع التحليل المقارب تخمينه في أي حال من الأحوال.

معدل النمو

يصف معدّل النمو Rate of growth مقدار التغير الحاصل في التعقيد الزمني لخوارزمية معينة وذلك بزيادة حجم المدخلات، ويُستخدم التعبير Big-O لتمثيل معدّل النمو ويتكوّن هذا التعبير من حرف O الكبير (ويرمز لكلمة "order") وصيغة معيّنة تعرض مقدار التعقيد الزمنية للخوارزمية. ويمكن أن تتضمّن الصيغة متغيرًا (يرمز له n) يمثّل حجم المدخلات.

هناك عدد كبير من الدوال التي تستخدم لتمثيل معدّل النمو ومن أهمّها:

الدالة الثابتة - O(1)‭‭‎

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

يكون التعقيد الزمني لدالة معينة (أو مجموعة من التعابير) مساويًا للدالة O(1)‎ إذا لم تتضمن حلقة تكرارية أو استدعاءً تعاوديًا أو استدعاءً لأي دالة أخرى ذات تعقيد زمني غير ثابت.

فمثلًا يبلغ التعقيد الزمني للدالة التالية المقدار O(1)‎:

public int GetCount(int[] items)
{
    return items.Length;
}

يمكن أن يبلغ التعقيد الزمني لدالة تحتوي على حلقة تكرارية أو استدعاء تعاودي المقدار O(1)‎ إن كانت الحلقة التكرارية أو الاستدعاءات التعاودية تتكرّر بمقدار ثابت، فعلى سبيل المثال، تمثّل c مقدارًا ثابتًا في الشيفرة التالية:

   for (int i = 1; i <= c; i++) {  
        // تعابير ذات تعقيد زمني ثابت
   }

الدالة الخطية - O(n)‭‎

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

يمكن تمييز الخورازميات ذات الدوال الخطية عن طريق الحلقات التكرارية التي تمر على جميع العناصر، والتي يزداد فيها متغير الحلقة التكرارية أو يتناقص بمقدار ثابت.

أمثلة:

public long GetSum(int[] items)
{
long sum = 0;
foreach (int i in items)
{
sum += i;
}
return sum;
}

   for (int i = 1; i <= n; i += c) {  
        // some O(1) expressions
   }

   for (int i = n; i > 0; i -= c) {
        // some O(1) expressions
   }

الدالة التربيعية - O(n^2)‭‎

يرتبط التعقيد الزمني في هذا النوع من الخوارزميات مع حجم المدخلات بعلاقة تربيعية. إن وقوع الخوارزمية في هذا الصنف يستدعي (في معظم الأحيان) إعادة النظر في عمل الخوارزمية أو في بنى المعطيات المستخدمة فيها. فعلى سبيل المثال تستغرق إجراء خوارزمية من هذا النوع على مصفوفة تحتوي على 1000 عدد صحيح إلى تنفيذ 1,000,000 عملية، والمصفوفة التي تحتوي على 1,000,000 عنصر ستحتاج إلى تنفيذ 1,000,000,000 (ترليون) عملية. ولتقريب الصورة أكثر سنفترض أنّ كل عملية تستغرق ملي ثانية فقط، وعلى هذا الفرض فإنّ الخوارزمية التي تستقبل مليون عنصرٍ ستستغرق 32 سنة لإتمام عملها، ولو زدنا سرعة هذه الخوارزمية 100 مرّة فإنّها ستستغرق 84 يومًا.

يساوي التعقيد الزمني للحلقات المتداخلة عدد المرات التي تنفّذ فيها العبارات في الحلقة الداخلية. يبلغ التعقيد الزمني في المثال التالي المقدار O(n^2)‎.

   for (int i = 1; i <=n; i += c) {
       for (int j = 1; j <=n; j += c) {
          // some O(1) expressions
       }
   }

   for (int i = n; i > 0; i -= c) {
       for (int j = i+1; j <=n; j += c) {
          // some O(1) expressions
   }

الدالة اللوغارتمية - O(log n)‭‎

الخوارزمية ذات الدالة اللوغارتمية هي خوارزمية يزداد فيها التعقيد الزمني لوغارتميًا مع حجم المدخلات. تدخل معظم الخوارزميات من نوع (فرّق تسد) ضمن هذا الصنف، وتضمّ أشجار البحث الثنائية توابع ودوال تستخدم خوارزميات ذات تعقيد زمني يبلغ O(log n)‎.

يبلغ التعقيد الزمني لحلقة تكرارية المقدار O(log n)‎ إن كان متغير الحلقة التكرارية يتضاعف أو يُقسّم على مقدار ثابت.

مثال:

 for (int i = 1; i <=n; i *= c) {
       // some O(1) expressions
   }
   for (int i = n; i > 0; i /= c) {
       // some O(1) expressions
   }

الدالة الخطية اللوغارتمية - O(n log n)‭‎

يبلغ التعقيد الزمني في الخوارزمية ذات الدالة الخطية اللوغارتمية linearithmic (تسمّى كذلك loglinear) المقدار O(n log n)‭.

تدخل بعض الخورزميات من نوع (فرّق تسد) في هذا الصنف، مثل خوارزمية التصنيف السريع quick sort والتصنيف الدمجي merge sort.

الحالات المُثلى والمتوسطة والسيئة

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

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

لذا يمكن القول أنّ الخوارزمية التي يبلغ تعقيدها الزمني O(n)‎ لن تبقى على هذا المقدار دائمًا، فقد يقلّ ولكنّه لن يزداد على الأغلب.

ما الذي يجري قياسه؟

إن قياس الخوارزميات وبنى المعطيات يعني عادة أحد الأمرين التاليين:

1. قياس الزمن الذي ستستغرقه الخوارزمية لإنهاء عملها (التعقيد العملي Operational Complexity).
2. مقدار المصادر (الذاكرة) التي تستهلكها تلك الخوارزمية (تعقيد المصادر Resorce compelxity).

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

هناك بعض الأمور التي يمكن قياسها ومنها:

• عمليات المقارنة (أكبر من، أصغر من، المساواة).
• عمليات الإسناد Assignments ومبادلة البيانات data swapping.
• حجز مواقع في الذاكرة Memory Allocations.

وعلى العموم فإنّ سياق العملية المنّفذة يعطي في العادة إشارة إلى نوع عملية القياس المجراة.

فعلى سبيل المثال عند الحديث عن التعقيد الزمني لخوارزمية تبحث عن عنصر معين في إحدى بنى المعطيات المعروفة، فإنّنا نتحدث بالتأكيد عن عمليات المقارنة، ولما كان البحث عملية للقراءة فقط read-only فمن المفترض أنّ لا تحتاج هذه العملية إلى إجراء عمليات إسناد أو حجز لمواقع في الذاكرة.

ولكن عند الحديث عن ترتيب البيانات وفرزها فإنّ من المنطقي أن نفترض بأنّنا نتحدث عن عمليات المقارنة والإسناد وحجز مواقع في الذاكرة.

مصادر

• الفصل الأول: Algorithms and Data Structures في كتاب Data Structures Succinctly Part 1، لمؤلفه Robert Horvick.