Algorithms/Asymptotic Analysis

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

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

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

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

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

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

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

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

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

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

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

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

تستخدم الرموز الثلاثة التالية استخدامًا واسعًا لتمثيل التعقيد الزمني للخوارزميات:

الرمز Θ

يحدّد الرمز Θ (ثيتا) الدالة من الأعلى والأسفل، لذا فإنّ هذا الرمز يصف السلوك المضبوط للخوارزمية، ويستخدم هذا الرمز عندما تكون الحالتان السوأى والفضلى متشابهتين.

الرمز Big O

يحدّد رمز O الكبيرة الحد الأعلى للخوارزمية، فعلى سبيل المثال تستغرق خوارزمية الترتيب بالإدراج Insertion Sort زمنًا خطّيًا في الحالة الفضلى، وتعقيدًا زمنيًا تربيعيًا في الحالة السوأى. ويمكن القول باطمئنان أن التعقيد الزمني لخوارزمية الترتيب بالإدراج هو O(n2)‎.

الرمز Ω

يحدّد رمز Ω الحد الأدنى للخوارزمية، ويعرض أسرع حل ممكن لتلك الخوارزمية.

تعرض الشيفرة التالية طريقة تنفيذ خوارزمية الترتيب بالفقاعات:

void bubble_sort(int array<a href='http://bigocheatsheet.com/' target='_blank' rel='nofollow'>], int n)
{
	// n عدد العناصر في المصفوفة المعطاة هو
	int temp;
	for(int i = 0; i < n-1; i++)
	{
		for(int j = 0; j < n-i-1; j++)
		{
			if (array[j] > array[j+1])
			{
				// مبادلة العناصر في الموقعين
				// j و j+1
				temp = array[j];
				array[j] = array[j+1];
				array[j+1] = temp;
			}
		}
	}
}

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

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

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

معدل النمو

يصف معدّل النمو 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(n2)‭‎

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

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

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(nlogn)‭‎

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

تدخل بعض الخورزميات التي تنتمي إلى أسلوب فرّق تسد في هذا الصنف، مثل خوارزمية الترتيب السريع 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 فمن المفترض أنّ لا تحتاج هذه العملية إلى إجراء عمليات إسناد أو حجز لمواقع في الذاكرة.

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

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

يمكن تشخيص الخوارزمية في ثلاث حالات:

1. الحالة السوأى
2. الحالة الوسطى
3. الحالة الفضلى

سنأخذ عملية البحث الخطّي كمثال لتوضيح هذه الحالات:

• C++‎:

#include <bits/stdc++.h> 
using namespace std; 

// البحث عن العنصر المعطى في المصفوفة المعطاة بطريقة خطية
// إن كان العنصر المعطى موجودًا أعدنا موقعه
// وإلا أعدنا -1
int search(int arr[], int n, int x) 
{ 
	int i; 
	for (i=0; i<n; i++) 
	{ 
	if (arr[i] == x) 
		return i; 
	} 
	return -1; 
} 

// اختبار الدالة السابقة
int main() 
{ 
	int arr[] = {1, 10, 30, 15}; 
	int x = 30; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	cout << x << " is present at index "
			<< search(arr, n, x); 

	getchar(); 
	return 0; 
}

• بايثون:

# البحث عن العنصر المعطى في المصفوفة المعطاة بطريقة خطية
# إن كان العنصر المعطى موجودًا أعدنا موقعه
# وإلا أعدنا -1
def search(arr, n, x): 
	i = 0
	for i in range(i, n): 
		if (arr[i] == x): 
			return i 
	return -1

# اختبار الدالة السابقة
arr = [1, 10, 30, 15] 
x = 30
n = len(arr) 
print(x, "is present at index", 
			search(arr, n, x))

• جافا:

// Java implementation of the approach 

public class GFG { 

// البحث عن العنصر المعطى في المصفوفة المعطاة بطريقة خطية
// إن كان العنصر المعطى موجودًا أعدنا موقعه
// وإلا أعدنا -1
	static int search(int arr[], int n, int x) { 
		int i; 
		for (i = 0; i < n; i++) { 
			if (arr[i] == x) { 
				return i; 
			} 
		} 
		return -1; 
	} 

	/* اختبار الدالة السابقة*/
	public static void main(String[] args) { 
		int arr[] = {1, 10, 30, 15}; 
		int x = 30; 
		int n = arr.length; 
		System.out.printf("%d is present at index %d", x, search(arr, n, x)); 

	} 
}

تحليل الحالة السوأى

يُحسب الحدّ الأعلى upper bound في وقت تشغيل الخوارزمية عند إجراء تحليل الحالة السوأى، ويجب معرفة الحالة التي تتسبب في إجراء أقصى عدد من العمليات. تحدث الحالة السوأى في المثال أعلاه (البحث الخطي) عندما لا يكون العنصر المراد البحث عنه (x في المثال السابق) موجودًا في المصفوفة التي ستجري فيها عملية البحث، وذلك لأنّ دالة البحث search()‎ ستقارن العنصر x مع جميع عناصر المصفوفة arr[]‎ واحدًا تلو الآخر؛ ولهذا فإنّ التعقيد الزمني للحالة الأسوا في عملية البحث الخطي يبلغ Θ(n)‎.

يجدر التنبيه إلى أنّ هذا النوع من التحليل هو الأكثر شيوعًا واعتمادًا.

تحليل الحالة الوسطى

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

تحليل الحالة الفضلى (التحليل الزائف)

يحسب التحليل الزائف الحدّ الأدنى lower bound في زمن تشغيل الخوارزمية، ويجب علينا في هذا النوع من التحليل معرفة الحالة التي تتسبب في إجراء أقل عدد من العمليات. تحدث الحالة الفضلى في المثال السابق (عملية البحث الخطي) عندما يكون العنصر x المراد البحث عنه في بداية المصفوفة التي ستجري فيها عملية البحث. يكون عدد العمليات في الحالة الفضلى ثابتًا (لا يعتمد على قيمة n)؛ ولهذا يكون التعقيد الزمني في الحالة الفضلى Θ(1)‎.

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

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

تحليل الحالة الفضلى هو تحليل زائف، ويضمن الحصول على الحدّ الأدنى من زمن تشغيل الخوارزمية ولا يقدم هذا أي معلومة مفيدة على خلاف تحليل الحالة السوأى، فقد تستغرق خوارزمية معينة سنوات لتؤدّي عملها.

هناك بعض الخوارزميات التي تكون فيها الحالات الثلاثة متماثلة، بمعنى أنّه لا وجود لحالة فضلى أو سوأى، فعلى سبيل المثال تؤدي خوارزمية الترتيب بالدمج Merge Sort عملها بتعقيد زمني قدره Θ(nLogn)‎ في جميع الحالات. لكن معظم خوارزميات البحث الأخرى تمتلك حالات فضلى وحالات سوأى، فمثلًا تحدث الحالة السوأى في التنفيذ الاعتيادي لخوارزمية الترتيب السريع Quick Sort (عندما يكون العنصر المحوري هو العنصر الأخير) عندما تكون المصفوفة المدخلة مرتّبة أصلًا، وتحدث الحالة الفضلى عندما تقسم العناصر المحورية المصفوفة إلى نصفين. وفي خوارزمية الترتيب بالإدراج Insertion Sort، تحدث الحالة السوأى عندما تكون المصفوفة المعطاة مرتّبة بالعكس، وتحدث الحالة الفضلى عندما تكون المصفوفة مرتبة بنفس ترتيب المخرجات.

مصادر

• الفصل الأول: Algorithms and Data Structures في كتاب Data Structures Succinctly Part 1، لمؤلفه Robert Horvick.
• صفحة Algorithm Performance في موقع freeCodeCamp.
• صفحة Asymptotic Notations في توثيق الخوارزميات في موقع GeeksforGeeks.