ملاحظات الخوارزميات للمحترفين تعقيد الخوارزميات Algorithms Complexity


محمد الميداوي

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

ترميز Big-Omega

تُستخدم ترميز Ω -notation لتمثيل المقارِب الأدنى asymptotic lower bound.

التعريف الرسمي

لتكن ‎fn)‎ و ‎g(n)‎ دالتين مُعرّفتين على مجموعة الأعداد الحقيقية الموجبة، فنقول أنّ ‎f(n) = Ω(g(n))‎ في حال وُجِدت ثابتان موجبان ‎c‎ و ‎n0‎ يحققان الآتي لكل n أكبر من أو تساوي n0:

 0  c g(n)  f(n)‎‎
اقتباس

ملاحظة: المعادلة f(n) = Ω(g(n))‎ تعني أنّ f(‎n‎)‎ لا يمكن أن تنمو تقاربيًا asymptotically بشكل أبطأ من ‎g(n)‎، كذلك يمكن كتابة ‎Ω(‎ g(‎ n ‎))‎ عندما لا يؤكّد تحليل الخوارزمية أنّ ‎Θ(g(n))‎ أو / ‎O(g(n))‎.

نظرية

بالنسبة لدالتين ‎f(n)‎ و ‎g(n)‎، نقول أنّ ‎f(n) = Ө(g(n))‎ فقط إذا كان الآتي محققًا:

  • f(n) = O(g(n))‎‎.
  • f(n) = Ω(g(n))‎.

يمكن تمثيل ترميز ‎Ω‎ بيانيًا على النحو التالي:

5qDtj.png

على سبيل المثال، إذا كانت
 

f(n) = 3n^2 + 5n - 4

فستكون ‎f(n) = Ω(n^2)‎، كما ستكون ‎f(n) = Ω(n)‎ أو حتى ‎‎f(n) = Ω(1)‎‎‎‎ صحيحة.

لدينا مثال آخر يحل خوارزمية التطابق التام matching algorithm، حيث إذا كان عدد الرؤوس vertices فرديًا، فسنحصل على الخرج "No Matching Matching"، وإلا فينبغي تجربة جميع التطابقات الممكنة.

وكنا نودّ القول أنّ الخوارزمية تتطلب وقتًا أسيًا exponential time، لكن الواقع أنه لا يمكنك إثبات وجود حدّ أدنى ‎Ω(n^2)‎ باستخدام التعريف المعتاد لـ ‎Ω‎ نظرًا لأنّ الخوارزمية تُجرى في وقت خطي linear time لقيم n الفردية.

وبدلًا من هذا فيجب علينا تعريف ‎f(n)=Ω(g(n))‎ على نحو أنه بالنسبة لثابت ‎‎c قيمته أكبر من الصفر، فهناك عدد لا نهائي من قيم ‎n‎ التي تحقّق الآتي:

f(n)≥ c g(n)

يوفّق هذا التعريف بين الحدّين الأعلى والأدنى إذ يحقّق التكافؤ الآتي:
 

f(n)=Ω(g(n))‎

فقط إن كان

f(n) != o(g(n))‎

ترميز Big-Theta

على خلاف ترميز Big-O الذي يمثل الحد الأعلى upper bound فقط من وقت تشغيل الخوارزميات، فإنّ ترميز Big-Theta هو رابط محصور Tight bound يشمل الحدّ العلوي والسفلي معًا، وهو أكثر دقة لكنه صعب الحساب.

وترميز Big-Theta متماثلة، أي تحقق المعادلة:
 

f(x) = Ө(g(x)) <=> g(x) = Ө(f(x))‎

 ولتفهم ذلك بسهولة، اعلم أن المعادلة الآتية
 

f(x) = Ө(g(x)) <=> g(x) = Ө(f(x))f(x) = Ө(g(x))‎

تعني أنّ الرسمين البيانيين للدالتين f و g ينمُوان بنفس المعدّل، أو أنّ الرسمين البيانيين "يتصرّفان" بشكل متماثل عند قيم x الكبيرة.

والتعبير الرياضي الكامل لترميز Big-Theta هو كما يلي:

Ө(f(x)) = {g: N0 -> R and c1, c2, n0 > 0}

حيث تكون

c1 < abs(g(n) / f(n))‎‎

لكل n أكبر من n0، وتمثل abs القيمة المطلقة.

ﻣﺜــــﺎل

إذا كانت الخوارزمية تأخذ العدد الآتي عمليةً للانتهاء مقابل مُدخل ‎n‎، فنقول أنّ تعقيدها يساوي ‎O(n^2)‎ ، كما يساوي أيضًا ‎O(n^3)‎ وO(n^100)‎. 
 

42n^2 + 25n + 4

أمّا في حال ترميز Big-Theta، فنقول أنّ التعقيد يساوي ‎Ө(n^2)‎، لكن لا يساوي ‎Ө(n^3)‎ أو ‎Ө(n^4)‎، إلخ… . كذلك، فإن كانت الخوارزمية من نوع ‎Ө(f(n))‎، فستكون أيضًا من النوع ‎O(f(n))‎، ولكن ليس العكس.

التعريف الرياضي

تُعرّف Ө(g(x))‎‎ على أنها مجموعة من الدوال، أما تعريفها الرياضي الرسمي Formal mathematical definition فهو:

Ө(g(x))‎‎‏ = f(x)}

وإذا كانت هناك ثوابت موجبة N وc1 و c2، بحيث يكون

0‎‎ <= c1*g(x) <= f(x) <= c2g*(x)‎‎

 لكل x أكبر من N}.

وهذا يعني أنّ Ө(g(x))‎‎ هي مجموعةٌ تحتوي كلّ دالة f مُحاصَرة من قبل الدالة g، بمعنى أنّه توجد 3 ثوابت موجبة هي c1 و c2 وN، بحيث يكون لدينا: 0‎‎ <= c1*g(x) <= f(x) <= c2*g(x)‎‎ لكل عدد x أكبر من N.

وبما أن ‎Ө(g(x))‎ مجموعةً فيمكننا كتابة الآتي ‎‎ للإشارة إلى أنّ ‎f(x)‎ تنتمي إلى ‎Ө(g(x))‎. 

f(x)  Ө(g(x))

غير أن الشائع هو كتابة الآتي للتعبير عن نفس الترميز:

 f(x) = Ө(g(x))‎

ويمكن تفسير ‎Ө(g(x))‎ عندما تظهر في ترميز ما على أنّها كناية عن دالة مجهولة لا تهمّنا تسميتها، فمثلًا، المعادلة الآتية:

T(n) = T(n/2) + Ө(n)‎

 تكافئ
 

T(n) = T(n/2) + f(n)‎

 حيث تمثّل ‎f(n)‎ دالةً ما من المجموعة ‎Ө(n)‎ا

وإن كانت ‎f‎ و ‎g‎ دالتين مُعرَّفتين على نفس النطاق من مجموعة الأعداد الحقيقية real numbers، فإننا نكتب  الآتي:
 

f(x) = Ө(g(x))‎

عندما تؤول x إلى ما لا نهاية x->infinity، وذلك فقط في حالة وجود ثابتْين موجبيْن K و L وعدد حقيقي x0 يحققون
 

K|g(x)| <= f(x) <= L|g(x)|‎‎

لكل x أكبر من أو تساوي x0.

يكون التعريف مكافئًا للعبارة التالية:

f(x) = O(g(x))‎‎

والعبارة:

f(x) = Ω(g(x))‎‎ 

استخدام مفهوم النهايات limits

إذا كان لدينا
 

limit(x->infinity) f(x)/g(x) = c  ( 0,∞)‎

 أي أنّ النهاية موجودة وموجبة، أي:
 

f(x) = Ө(g(x))

وفيما يلي بعض أصناف التعقيد الشائعة:

الاسم الترميز n = 10 n = 100
Constant - ثابت Ө(1) 1 1
Logarithmic - لوغارتمي Ө(log(n)) 3 7
Linear - خطي Ө(n) 10 100
Linearithmic - لوغارتمي-خطي Ө(n*log(n)) 30 700
Quadratic - تربيعي Ө(n^2) 100 10000
Exponential - أسّي Ө(2^n) 1024 1.267650e+ 30
Factorial - مُعاملي Ө(n!) 3 628 800 9.332622e+157

موازنة الصيغ المقاربة asymptotic notations

لتكن ‎f(n)‎ و ‎g(n)‎ دالتين مُعرّفتين على مجموعة الأعداد الحقيقية الموجبة، ولتكن ‎c, c1, c2, n0‎ ثوابت حقيقية موجبة.

يوضّح الجدول التالي الفروق بين مختلف الصيغ:

الترميز f(n) = O(g(n)) f(n) = Ω(g(n)) f(n) = Θ(g(n)) f(n) = o(g(n)) f(n) = ω(g(n))
التعريف الرسمي ∃ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ f(n) ≤ c g(n) ∃ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ c g(n) ≤ f(n) ∃ c1, c2 > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ c1 g(n) ≤ f(n) ≤ c2 g(n) ∀ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ f(n) < c g(n) ∀ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ c g(n) < f(n)
التشابه مع الموازنة بين عددين a وb a ≤ b a ≥ b a = b a < b a > b
أمثلة 7n + 10 = O(n^2 + n - 9) n^3 - 34 = Ω(10n^2 - 7n + 1) 1/2 n^2 - 7n = Θ(n^2) 5n^2 = o(n^3) 7n^2 = ω(n)
الرسوم البيانية  
AkEKr.png  
5qDtj.png  
RPdzC.png  
   

يمكن تمثيل الصيغ المُقارِبة بواسطة مخطّط فِن كما يلي:

v2eH3.png

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

اقرأ أيضًا





تفاعل الأعضاء


لا توجد أيّة تعليقات بعد



يجب أن تكون عضوًا لدينا لتتمكّن من التعليق

انشاء حساب جديد

يستغرق التسجيل بضع ثوان فقط


سجّل حسابًا جديدًا

تسجيل الدخول

تملك حسابا مسجّلا بالفعل؟


سجّل دخولك الآن