البحث في الموقع

تستعرض هذه المقالة مفهوم التعقيد 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) = Ө(g(n))‎ فقط إذا كان الآتي محققًا: f(n) = O(g(n))‎‎. f(n) = Ω(g(n))‎. يمكن تمثيل ترميز ‎Ω‎ بيانيًا على النحو التالي: على سبيل المثال، إذا كانت ‎ 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)) ‎ وفيما يلي بعض أصناف التعقيد الشائعة: table { width: 100%; } thead { vertical-align: middle; text-align: center; } td, th { border: 1px solid #dddddd; text-align: right; padding: 8px; text-align: inherit; } tr:nth-child(even) { background-color: #dddddd; } الاسم الترميز 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) الرسوم البيانية يمكن تمثيل الصيغ المُقارِبة بواسطة مخطّط فِن كما يلي: ترجمة -بتصرّف- للفصل الثاني من كتاب Algorithms Notes for Professionals اقرأ أيضًا المقالة السابقة: مدخل إلى الخوارزميات دليل شامل عن تحليل تعقيد الخوارزمية بناء مصنف بالاعتماد على طرق تعلم الآلة بلغة بايثون باستخدام مكتبة Scikit-Learn النسخة الكامة من كتاب مدخل إلى الذكاء الاصطناعي وتعلم الآلة