دليل شامل عن تحليل تعقيد الخوارزمية

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

يستهدف هذا المقال المبرمجين الذين يعرفون عملهم جيدًا ولكنهم لا يملكون خلفيةً نظريةً في علوم الحاسوب، وذلك من خلال واحدة من أكثر أدوات علوم الحاسوب واقعيةً، وهي: صيغة O الكبير Big O notation، وتحليل تعقيد الخوارزمية algorithm complexity.

تُعَدّ هذه الأداة واحدةً من الأدوات المفيدة عمليًا للأشخاص العاملين في المجال الأكاديمي لعلوم الحاسوب، وفي إنشاء برامج على مستوى الإنتاج في الصناعة، لذلك نأمل أن تتمكن من تطبيقها في الشيفرة الخاصة بك لتحسينها بعد قراءة هذا المقال، كما يُفتَرض أن تكون قادرًا على فهم جميع المصطلحات الشائعة التي يستخدمها المختصون في علوم الحاسوب، مثل مصطلحات: التعقيد "Big O"، و"السلوك المقارب asymptotic behavior"، و"تحليل الحالة الأسوأ worst-case analysis" بعد قراءة هذا المقال.

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

لا يحتوي هذا المقال على أي متطلبات رياضية مسبقَة، كما سيمنحك الخلفية التي ستحتاجها لمواصلة دراسة الخوارزميات مع فهمٍ أقوى للنظرية الكامنة وراءها، وننصح الأشخاص الذين يشاركون في هذه المسابقات الطلابية بشدة بقراءة هذا المقال التمهيدي بأكمله ومحاولة فهمه تمامًا، لأنه سيكون ضروريًا أثناء دراسة الخوارزميات وتعلُّم المزيد من التقنيات المتقدِّمة.

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

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

لا تحتاج إلى خلفية رياضية لأن النص الأصلي لهذا المقال قد استهدف طلاب المدارس الثانوية، لذلك سيكون أي شخصٍ لديه بعض الخبرة في البرمجة -أي إن عرف ما هي العَودية recursion على سبيل المثال- قادرًا على المتابعة دون أي مشكلة.

ستجد خلال هذا المقال العديد من الروابط التي تنقلك للاطلاع على مواد مهمة خارج نطاق موضوع المقال، إذ يُحتمل درايتك بمعظم هذه المفاهيم إذا كنت مبرمجًا صناعيًا؛ أما إذا كنت طالبًا مشاركًا في المسابقات، فسيعطيك اتباع هذه الروابط أفكارًا حول مجالات أخرى من علوم الحاسوب أو هندسة البرمجيات التي ربما لم تستكشفها بعد، والتي يمكنك الاطلاع عليها لتوسيع اهتماماتك.

يصعب على الكثير من المبرمجين والطلاب فهم تحليل تعقيد الخوارزمية وصيغة Big O، أو يخافون منه، أو يتجنبونه تمامًا ويعدّونه عديم الفائدة، لكنه ليس صعبًا أو نظريًا كما قد يبدو للوهلة الأولى.

يُعَدّ تعقيد الخوارزمية طريقةً لقياس سرعة تشغيل برنامج ما أو خوارزمية ما، لذلك يُعَد أمرًا عمليًا.

الدافع Motivation

يوجد أدوات لقياس مدى سرعة تشغيل البرنامج، فهناك برامج تسمى المشخِّصات profilers، حيث تقيس وقت التشغيل بالميلي ثانية ويمكنها مساعدتنا في تحسين الشيفرة الخاصة بنا عن طريق تحديد الاختناقات bottlenecks، وعلى الرغم من فائدة هذه الأداة إلا أنها ليست ذات صلة فعلية بتعقيد الخوارزمية، فتعقيد الخوارزمية مصمَّمٌ لمقارنة خوارزميتين ضمن المستوى المثالي، أي تجاهل التفاصيل منخفضة المستوى، مثل: لغة برمجة التطبيق، أو العتاد الذي تعمل عليه الخوارزمية، أو مجموعة تعليمات وحدة المعالجة المركزية CPU.

عندما نريد مقارنة الخوارزميات من حيث ماهيتها -أي الأفكار التي تُعرّفنا كيفية حساب شيءٍ ما-، فلن يساعدنا العد بالميلي ثانية في ذلك، إذ يُحتمَل أن تعمل الخوارزمية السيئة والمكتوبة بلغة برمجة منخفضة المستوى مثل لغة التجميع Assembly، بصورة أسرع بكثير من خوارزمية جيدة مكتوبة بلغة برمجة عالية المستوى مثل بايثون، أو روبي، لذلك يجب تحديد معنى "الخوارزمية الأفضل".

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

تتضمن أمثلة العمليات الحسابية البحتة العمليات العشرية العددية numerical floating-point operations، مثل: الجمع والضرب، أو البحث داخل قاعدة بيانات متناسبة مع الذاكرة العشوائية RAM عن قيمة معينة، أو تحديد المسار الذي ستمر به شخصية ذكاء اصطناعي في لعبة فيديو، بحيث يتعين عليها فقط السير مسافةً قصيرةً داخل عالمها الافتراضي (كما في الشكل الآتي)، أو تشغيل تطابق نمط تعبير نمطي regular expressions مع سلسلة، فالعمليات الحسابية موجودة في كل مكان في البرامج الحاسوبية.

تستخدم شخصيات الذكاء الاصطناعي في ألعاب الفيديو الخوارزميات لتجنب العقبات عند تنقّلها في العالم الافتراضي

يُعَدّ تحليل التعقيد أداةً لشرح كيفية تصرّف الخوارزمية مع زيادة حجم الدخل. وهنا نتساءل، إذا زدنا الدخل، فكيف ستتصرّف الخوارزمية؟ أي إذا كانت الخوارزمية الخاصة بنا تستغرق ثانيةً واحدةً للتشغيل بالنسبة إلى دخلٍ بحجم 1000، فكيف ستتصرف الخوارزمية إذا ضاعفنا حجم الدخل؟ هل ستعمل بالسرعة نفسها، أم بنصف السرعة، أم أبطأ بأربع مرات؟ يُعَدّ هذا مهمًا في البرمجة العملية لأنه سيسمح لنا بالتنبؤ بسلوك الخوارزمية عندما تصبح بيانات الدخل أكبر؛ فمثلًا، إذا أنشأنا خوارزميةً لتطبيق ويب يعمل جيدًا مع 1000 مستخدِم، وقِسنا وقت تشغيله باستخدام تحليل تعقيد الخوارزمية، فيمكننا توقُّع ما سيحدث بمجرد حصولنا على 2000 مستخدِم بدلًا من ذلك.

يمنحنا تحليل التعقيد في مسابقات الخوارزميات رؤيةً عن المدة التي سيستغرقها تشغيل الشيفرة لأكبر حالات الاختبار التي تُستخدَم لاختبار صحة البرنامج، لذلك إذا قِسنا سلوك برنامجنا مع دخل صغير، فسنعرف سلوكه مع الدخل الأكبر.

لنبدأ بمثال بسيط هو إيجاد العنصر الأكبر في مصفوفة.

عد التعليمات

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

إذا كنت طالبًا منافسًا في مسابقات الخوارزميات، فيُرجَّح استخدمك لغة C++‎، لذلك لن تواجه مشكلة، وبالتالي نوصي في هذه الحالة التدرّب باستخدام لغة C++‎.

يمكن البحث عن العنصر الأكبر في مصفوفة باستخدام شيفرة لغة جافا سكريبت التالية، بافتراض أن مصفوفة الدخل هي A، وحجمها n:

var M = A[ 0 ];

for ( var i = 0; i < n; ++i ) {
   if ( A[ i ] >= M ) {
       M = A[ i ];
   }
}

أول شيء سنفعله هو حساب عدد التعليمات الأساسية التي ينفذها هذا الجزء من الشيفرة، حيث سنفعل هذا مرةً واحدةً فقط، ولن يكون ضروريًا لاحقًا، لذلك تحمَّل لبضع لحظات.

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

• إسناد قيمة لمتغير.
• البحث عن قيمة عنصر معين في مصفوفة.
• مقارنة قيمتين.
• زيادة قيمة.
• العمليات الحسابية الأساسية، مثل: الجمع، والضرب.

سنفترض أن التفرع -أي الاختيار بين جزئي if وelse بعد تقييم شرط if- سيحدث على الفور ولن يحسب هذه التعليمات.

السطر الأول من الشيفرة السابقة هو:

var M = A[ 0 ];

يتطلب هذا السطر تعليمتين: إحداهما للبحث عن العنصر A[ 0 ]، والأخرى لإسناد قيمته إلى M، حيث سنفترض أن قيمة n تساوي 1 على الأقل دائمًا، كما تتطلّب الخوارزمية هاتين التعليمتين دائمًا، بغض النظر عن قيمة n، ويجب أيضًا تشغيل شيفرة تهيئة حلقة for دائمًا، ويعطينا هذا تعليمتين أخريين، هما: الإسناد assignment، والمقارنة comparison:

i = 0;
i < n;

ستشغَّل هاتان التعليمتان قبل أول تكرار من حلقة for، كما نحتاج إلى تعليمتين إضافيتين للتشغيل بعد كل تكرار لحلقة for، وهما: زيادة المتغير i، ومقارنة للتحقق من أننا ما زلنا ضمن الحلقة، أي كما يلي:

++i;
i < n;

إذا تجاهلنا جسم الحلقة، فسيكون عدد التعليمات التي تحتاجها هذه الخوارزمية هو 4 + 2n، أي 4 تعليمات في بداية حلقة for، وتعليمتين في نهاية كل تكرار من n تكرار. يمكننا الآن تحديد دالة رياضية f( n )، حيث تعطينا عدد التعليمات التي تحتاجها الخوارزمية عند إعطاء n، أي لدينا f( n ) = 4 + 2n عندما يكون جسم حلقة for فارغًا.

تحليل الحالة الأسوأ Worst-case analysis

لدينا بالنظر إلى جسم حلقة for عملية بحث في مصفوفة، وعملية مقارنة تحدث دائمًا، كما يلي:

if ( A[ i ] >= M ) { …

أي يوجد تعليمتان، ولكن اعتمادًا على قيم المصفوفة، فقد يعمل جسم تعليمة if وقد لا يعمل. فإذا تحقق A[ i ] >= M، فسنشغّل هاتين التعليمتين الإضافيتين -أي البحث في مصفوفة والإسناد-، كما يلي:

M = A[ i ]

لكن لا يمكننا الآن تحديد الدالة f( n ) بسهولة، وذلك لعدم اعتماد عدد التعليمات على n فقط، وإنما على الدخل أيضًا، فإذا كان الدخل A = [ 1, 2, 3, 4 ] مثلًا، فستحتاج الخوارزمية إلى تعليمات أكثر مما إذا كان الدخل A = [ 4, 3, 2, 1 ].

نفكر عند تحليل الخوارزميات في أسوأ سيناريو غالبًا، فما هو أسوأ شيء يمكن حدوثه لخوارزميتنا؟ ومتى تحتاج الخوارزمية إلى معظم التعليمات لإكمالها؟ في هذه الحالة، يحدث ذلك عندما يكون لدينا مصفوفة بترتيب تصاعدي مثل A = [ 1, 2, 3, 4 ]، حيث يجب استبدال المتغير M في كل مرة، وبالتالي، سينتج عن ذلك تنفيذ معظم التعليمات، ويُطلَق على هذه الحالة اسم تحليل الحالة الأسوأ Worst-case analysis؛ وهذا ليس أكثر من مجرد التفكير في الحالة التي تحدث عندما نكون الأقل حظًا.

لدينا في أسوأ الحالات 4 تعليمات للتشغيل داخل جسم حلقة for، لذلك لدينا f( n ) = 4 + 2n + 4n = 6n + 4، حيث تعطينا الدالة f عدد التعليمات التي قد تكون مطلوبةً في الحالة الأسوأ بالاعتماد على حجم المشكلة n.

السلوك المقارب Asymptotic behavior

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

يعتمد عدد تعليمات وحدة المعالجة المركزية الفعلية اللازمة لكل عبارة لغة برمجة، على مُصرِّف compiler لغة البرمجة، وكذا على مجموعة تعليمات وحدة المعالجة المركزية المتاحة، سواءً كان معالج AMD أو Intel Pentium على حاسوبك، أو كان معالج MIPS على Playstation 2 الخاصة بك، وسنتجاهل ذلك أيضًا كما ذكرنا سابقًا.

سنشغّل الآن الدالة "f" الخاصة بنا من خلال "مرشِّح filter" ليساعدنا في التخلص من التفاصيل الصغيرة التي يفضّل المتخصصون في علوم الحاسوب تجاهلها.

يوجد قسمان في الدالة f التي تساوي 6n + 4، وهما: 6n، و4، كما لا نهتم في تحليل التعقيد إلا بما يحدث لدالة عد التعليمات عندما يكبر دخل البرنامج (n)، ويتماشى هذا مع الأفكار السابقة لسلوك "السيناريو الأسوأ" الذي ينص على الاهتمام بكيفية تصرّف الخوارزمية عند معالجتها بصورة سيئة، أي عندما تفعل هذه الخوارزمية شيئًا صعبًا، وهذا مفيد حقًا عند مقارنة الخوارزميات.

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

سنحذف الأقسام التي تنمو ببطء ونبقي فقط الأقسام التي تنمو بسرعة عندما تصبح n أكبر، ومن الواضح أن 4 ستبقى 4 لأن n تنمو بصورة أكبر؛ أما 6n فتنمو بصورةٍ أكبر وأكبر، لذلك تميل إلى كونها أهم بالنسبة للمشكلات الأكبر، وبالتالي، أول شيء سنفعله هو حذف 4 والاحتفاظ بالدالة على صورة f( n ) = 6n.

يُعَدّ ما سبق منطقيًا، وذلك لأنّ الرقم 4 هو "ثابت التهيئة initialization constant" ببساطة، وقد تتطلب لغات البرمجة المختلفة وقتًا مختلفًا لعملية الإعداد، فمثلًا، تحتاج لغة جافا إلى بعض الوقت لتهيئة آلتها الافتراضية virtual machine، وبما أننا نتجاهل الاختلافات في لغات البرمجة، فمن المنطقي تجاهل هذه القيمة فقط.

الشيء الثاني الذي سنتجاهله هو معامل الضرب الثابت أمام n، وبالتالي ستصبح الدالة f( n ) = n، مما يجعل الأمور أكثر بساطةً.

يُعَدّ إهمال معامل الضرب أمرًا منطقيًا إذا فكرنا في كيفية تصريف لغات البرمجة المختلفة، فقد تُصرَّف عبارة "البحث في المصفوفة" في إحدى لغات البرمجة إلى تعليمات مختلفة عن لغات برمجةٍ مختلفة، كما لا يتضمّن الإجراء A[ i ] التحقق من عدم تجاوز المتغير i لحجم المصفوفة المُصرَّح عنها في لغة سي C على سبيل المثال، ولكنه يتضمّن ذلك في لغة باسكال Pascal؛ إذًا فالشيفرة التالية المكتوبة بلغة باسكال:

M := A[ i ]

تكافئ الشيفرة التالية المكتوبة بلغة سي:

if ( i >= 0 && i < n ) {
   M = A[ i ];
}

لذلك نتوقّع أن لغات البرمجة المختلفة ستنتج عوامِلًا مختلفةً عندما نعُد تعليماتها.

تستخدِم لغة باسكال مصرِّفًا غبيًا يغفَل عن التحسينات الممكنة في هذا المثال، كما تتطلب ثلاث تعليمات لكل وصول إلى مصفوفة، في حين تتطلب لغة سي تعليمةً واحدةً.

يُطبَّق إهمال هذا العامل على جميع الاختلافات بين لغات البرمجة والمصرِّفات أيضًا، وبالتالي، تُحلَّل فكرة الخوارزمية فقط.

يُسمَّى المرشِّح المتمثِّل بعمليتَي "إهمال جميع العوامل"، و"الإبقاء على القسم الذي يكبر أكثر" كما هو موصوف أعلاه بالسلوك المقارب asymptotic behavior، ولذلك نمثِّل السلوك المقارب للدالة f( n ) = 2n + 8 من خلال الدالة f( n ) = n.

نهتم رياضيًا بنهاية الدالة f لأن n يميل إلى اللانهاية؛ ولكن إن لم تفهم ما تعنيه هذه العبارة، فلا تقلق لأنّ هذا كل ما تحتاج إلى معرفته، كما لن نستطيع إهمال الثوابت في النهاية في إطار رياضي صارم، ولكننا نفعل ذلك لأغراض علوم الحاسوب وللأسباب الموضَّحة أعلاه.

سنحل بعض الأمثلة لفهم الفكرة أكثر، فمثلًا، لنجد السلوك المقارب لدوال المثال التالي بإهمال العوامِل الثابتة، والحفاظ على الأقسام التي تكبر بسرعة:

1. تعطي الدالة f( n ) = 5n + 12 الدالة f( n ) = n باستخدام الاستنتاج نفسه بالضبط كما هو مذكور أعلاه.
2. تعطي الدالة f (n) = 109 الدالة f( n ) = 1، حيث سنهمل معامل الضرب 109 * 1، لكن لا يزال يتعين علينا وضع 1 هنا للإشارة إلى أنّ لهذه الدالة قيمة غير صفرية.
3. تعطي الدالة f( n ) =n² + 3n + 112 الدالة f( n ) = n²، حيث تكبرn² أكثر من 3n بالنسبة لقيمة n كبيرة بدرجة كافية، لذلك نحتفظ بها.
4. تعطي الدالة f( n ) = n³ + 1999n + 1337 الدالة f( n ) = n³، فعلى الرغم من أنّ العامل الموجود أمام n كبير جدًا، لكن لا يزال بإمكاننا العثور على قيمة n كبيرة بما يكفي، بحيث يكون n³ أكبر من 1999n، وبما أننا مهتمون بسلوك قيم n الكبيرة جدًا، فسنبقي على n³ فقط، أي تصبح الدالة n³ المرسومة باللون الأزرق في الشكل التالي أكبر من الدالة 1999n المرسومة باللون الأحمر بعد القيمة n = 45، كما تبقى هي الأكبر بعد هذه النقطة إلى الأبد.

5. تعطي الدالة f( n ) = n +√n الدالة f (n) = n، وذلك لأنّ n تنمو أسرع من ‎√n كلما زادتn ويمكنك تجربة الأمثلة الآتية بنفسك.

تمرين 1

1. f( n ) = n⁶ + 3n
2. f( n ) = 2ⁿ + 12
3. f( n ) = 3ⁿ + 2ⁿ
4. f( n ) = nⁿ + n

(اكتب نتائجك، وسترى الحل أدناه).

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

التعقيد Complexity

بما أنه يمكننا إهمال كل هذه الثوابت "الشكلية"، فمن السهل جدًا معرفة السلوك المقارب لدالة عدّ تعليمات البرنامج، حيث يملك البرنامج الذي لا يحتوي على حلقات، الدالة f( n ) = 1، لأن عدد التعليمات التي يحتاجها هو مجرد عددٍ ثابت -إلا في حالة استخدامه العودية كما سنرى لاحقًا-.

يملك البرنامج الذي يحتوي حلقةً واحدةً تمتد من 1 إلى n، الدالة f( n ) = n، حيث سينفِّذ عددًا ثابتًا من التعليمات قبل الحلقة، وعددًا ثابتًا من التعليمات بعد الحلقة، وعددًا ثابتًا من التعليمات داخل الحلقة التي تُشغَّل جميعًا n مرة.

يجب أن يكون هذا أكثر سهولةً وأقل مللًا من عدّ التعليمات الفردية، لذلك لنلقِ نظرةً على بعض الأمثلة لفهم ذلك أكثر. يتحقق البرنامج التالي المكتوب بلغة PHP من وجود قيمة معيَّنة داخل مصفوفة A لها الحجم n:

<?php
   $exists = false;
   for ( $i = 0; $i < n; ++$i ) {
       if ( $A[ $i ] == $value ) {
           $exists = true;
           break;
       }
   }
?>

تسمَّى هذه الطريقة للبحث عن قيمة داخل مصفوفة البحث الخطي linear search، وهذا اسم معقول لاحتواء هذا البرنامج على الدالة f( n ) = n، كما سنحدد بالضبط ما تعنيه كلمة "خطي" في القسم التالي.

لاحظ وجود عبارة "break" هنا، والتي قد تؤدّي إلى إنهاء البرنامج في وقت قريب، وربما بعد تكرارٍ واحد؛ لكن تذكّر اهتمامنا بالسيناريو الأسوأ، وهو بالنسبة لهذا البرنامج عدم احتواء المصفوفة A على القيمة التي نبحث عنها، لذلك لا يزال لدينا الدالة f( n ) = n.

تمرين 2

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

لنلقِ نظرةً على البرنامج المكتوب بلغة بايثون Python، والذي يجمع عنصرين من مصفوفة معًا لينتج مجموع يُخزَّن في متغير آخر:

v = a[ 0 ] + a[ 1 ]

لدينا هنا عددٌ ثابت من التعليمات، لذلك f (n) = 1.

يتحقق البرنامج التالي المكتوب بلغة C++‎ من احتواء متّجه -مصفوفة مختارة أو جزء من مصفوفة- يُسمَّى A، وذو حجم n على قيمتين متماثلتين في أي مكان ضمنه:

bool duplicate = false;
for ( int i = 0; i < n; ++i ) {
   for ( int j = 0; j < n; ++j ) {
       if ( i != j && A[ i ] == A[ j ] ) {
           duplicate = true;
           break;
       }
   }
   if ( duplicate ) {
       break;
   }
}

بما أنه توجد هنا حلقتان متداخلتان داخل بعضهما البعض، فسيكون لدينا سلوكًا مقاربًا موصوفًا بالدالة f( n ) = n².

اقتباس

قاعدة عامة: يمكن تحليل البرامج البسيطة عن طريق عدّ الحلقات المتداخلة في البرنامج، بحيث تنتج حلقة مفردة مارة على n عنصر الدالة f( n ) = n، وتنتج حلقة داخل حلقة الدالةf( n ) = n²، كما تنتج حلقة داخل حلقة داخل حلقة الدالة f (n) = n³.

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

لنلقِ نظرةً على المثال التالي المكتوب بلغة ?

int i;
for ( i = 0; i < n; ++i ) {
   f( n );
}

إذا علمنا أن f( n ) هي دالة تنفِّذ n تعليمة بالضبط، فيمكننا حينئذٍ معرفة أن عدد تعليمات البرنامج بأكمله هو n² بصورةٍ مقاربة، حيث تُستدعى الدالة n مرة تمامًا.

اقتباس

قاعدة عامة: إذا كان لدينا سلسلة من حلقات for المتسلسلة، فستحدِّد أبطأ حلقة سلوك البرنامج المقارب، وإذا وُجِدت حلقتان متداخلتان متبوعتان بحلقةٍ واحدة، فهذا يكافئ وجود الحلقات المتداخلة وحدها فقط، وذلك لأنّ الحلقات المتداخلة ستطغى على الحلقة البسيطة.

ننتقل الآن إلى الصيغة التخيُّلية التي يستخدمها علماء الحاسوب للسلوك المقارب، حيث سنقول أن برنامجنا هو Θ ( f( n )) عندما نحدِّد الدالة f بصورة مقاربة، فمثلًا، البرامج المذكورة أعلاه هي Θ (1) وΘ( n² ) وΘ( n²  ) على التوالي، حيث تُقرَأ Θ( n ) "ثيتا بالنسبة إلى n".

نقول أحيانًا أنّ f( n ) -وهي الدالة الأصلية التي تحسب عدد التعليمات بما في ذلك الثوابت- هي شيء ما Θ، حيث نقول مثلًا أنّ f( n ) = 2n هي دالة Θ( n )، كما يمكننا كتابة 2n ∈ Θ (n)‎ أيضًا، والتي تُنطَق "2n هي ثيتا بالنسبة إلى n".

لا ترتبك بشأن هذا الصيغة، فكل ما تنص عليه هو أنه إذا حسبنا عدد التعليمات التي يحتاجها البرنامج وهي 2n، فسيُوصَف السلوك المقارب للخوارزمية بـ n والذي نتج بإهمال الثوابت.

فيما يلي بعض العبارات الرياضية الصحيحة باستخدام هذا الصيغة:

1. n⁶ + 3n ∈ Θ( n⁶ )
2. 2ⁿ + 12 ∈ Θ( 2ⁿ )
3. 3ⁿ + 2ⁿ ∈ Θ( 3ⁿ )
4. nⁿ + n ∈ Θ( nⁿ )

بالمناسبة، إذا حللت التمرين 1 السابق، فهذه هي بالضبط الإجابات التي يجب أن تصل إليها.

نسمّي ما نضعه ( هنا )Θ التعقيد الزمني time complexity، أو تعقيد complexity الخوارزمية، لذلك فللخوارزمية التي تحتوي على الصيغة Θ( n ) تعقيدٌ هو n.

لدينا أيضًا أسماءً خاصةً للصيغ التالية: Θ( 1 )، وΘ( n )، وΘ( n² ) وΘ( log( n ) )، وذلك لكثرة ظهورها، حيث نقول أنّ خوارزمية Θ( 1 ) هي خوارزمية ذات وقت ثابت constant-time algorithm، والخوارزمية Θ( n ) خطية linear، وΘ( n² ) تربيعية quadratic؛ أما الخوارمية Θ( log( n ) )  فهي لوغاريتمية logarithmic. لا تقلق إن لم تعرف ما هي اللوغاريتمات حتى الآن، سنشرح ذلك لاحقًا.

اقتباس

قاعدة عامة: تعمل البرامج ذات صيغة Θ الأكبر بصورةٍ أبطأ من البرامج ذات صيغة Θ الأصغر.

صيغة O الكبير Big-O notation

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

مشكلة الفرز (sorting problem) هي إحدى المشكلات الشهيرة التي يستخدمها علماء الحاسوب لتدريس الخوارزميات، حيث تُعطَى مصفوفة A بحجم n في مشكلة الفرز، ويُطلَب منا كتابة برنامج لفرز أو ترتيب هذه المصفوفة، وتُعَدّ هذه المشكلة مشكلةً مهمةً كونها مشكلةً واقعيةً في الأنظمة الحقيقية، إذ يحتاج مستكشف الملفات إلى فرز الملفات التي يعرضها حسب الاسم حتى يتمكن المستخدِم من التنقل بينها بسهولة، أو قد تحتاج لعبة فيديو إلى فرز الكائنات ثلاثية الأبعاد المعروضة في العالم بناءً على بعدها عن عين اللاعب داخل العالم الافتراضي من أجل تحديد ما هو مرئي وما هو غير مرئي، وهو ما يسمى مشكلة الرؤية Visibility Problem، فالكائنات التي تكون أقرب للاعب هي المرئية، في حين أنّ الكائنات البعيدة قد تخفيها الكائنات الموجودة أمامها، ويوضّح الشكل الآتي هذه المشكلة، إذ لن يرى اللاعب الموجود في النقطة الصفراء المناطق المظلَّلة، كما يُعَدّ تقسيم العالم إلى أجزاء صغيرة وفرزها حسب المسافة التي تفصلها عن اللاعب إحدى طرق حل مشكلة الرؤية.

يُعَدّ الفرز أيضًا مهمًا بسبب وجود العديد من الخوارزميات لحله، كما يكون بعضها أسوأ من البعض الآخر، وهي أيضًا مشكلة سهلة التحديد والشرح، لذلك لنكتب جزءًا من شيفرة تفرز مصفوفة.

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

b = []
n.times do
   m = a[ 0 ]
   mi = 0
   a.each_with_index do |element, i|
       if element < m
           m = element
           mi = i
       end
   end
   a.delete_at( mi )
   b << m
end

تسمى هذه الطريقة الفرز الانتقائي Selection sort، حيث تجد هذه الخوارزمية الحد الأدنى من المصفوفة -يُرمَز إلى المصفوفة بالمتغير a في الشيفرة السابقة، بينما يُرمَز إلى الحد الأدنى بالمتغير m، والمتغير mi هو دليله في المصفوفة-، وتضعه في نهاية مصفوفة جديدة -أي المصفوفة b في حالتنا-، ثم تزيله من المصفوفة الأصلية، وبعدها تجد الحد الأدنى بين القيم المتبقية للمصفوفة الأصلية، وتلحِقه بالمصفوفة الجديدة التي تحتوي على عنصرين الآن، ثم تزيله من المصفوفة الأصلية؛ وتستمر هذه العملية إلى حين إزالة جميع العناصر من المصفوفة الأصلية وإدخالها في المصفوفة الجديدة، مما يعني فرز المصفوفة.

نلاحظ وجود حلقتين متداخلتين في الشيفرة السابقة، حيث تعمل الحلقة الخارجية n مرة، وتعمل الحلقة الداخلية مرةً واحدةً لكل عنصر من عناصر المصفوفة a. تحتوي المصفوفة a في البداية على n عنصر، ونزيل عنصر مصفوفة واحد في كل تكرار، لذلك تتكرر الحلقة الداخلية n مرة خلال التكرار الأول للحلقة الخارجية، ثم n - 1 مرة، وبعدها n - 2 مرة، وهكذا دواليك حتى التكرار الأخير للحلقة الخارجية التي تعمل خلالها مرةً واحدةً فقط.

من الصعب قليلًا تقييم تعقيد هذا البرنامج، حيث يجب معرفة المجموع 1 + 2 + … +(n+(n-1، ولكن يمكننا بالتأكيد إيجاد "الحد الأعلى" لهذا المجموع، وهذا يعني أنه يمكننا تغيير برنامجنا - أي يمكنك فعل ذلك في عقلك، وليس في الشيفرة الفعلية- لجعله أسوأ مما هو عليه، ومن ثم إيجاد تعقيد هذا البرنامج الجديد، فإذا تمكّنا من العثور على تعقيد البرنامج الأسوأ الذي أنشأناه، فسنعلم أنّ برنامجنا الأصلي أسوأ أو ربما أفضل. بالتالي إذا أوجدنا تعقيدًا جيدًا لبرنامجنا المعدَّل الذي هو أسوأ من برنامجنا الأصلي، فيمكننا معرفة أنه سيكون لبرنامجنا الأصلي تعقيدًا جيدًا جدًا أيضًا، أي إما جيدًا بمستوى برنامجنا المعدَّل أو أفضل منه.

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

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

تُنطَق O( n² ) "أوه كبيرة لمربع n، أي big oh of n squared"، وهذا يقودنا للقول بأن برنامجنا ليس أسوأ من n² بصورةٍ مقاربة، فقد يكون أفضل من ذلك أو مثله.

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

قد لايكون البرنامج O( n² ) هو Θ( n² ) أيضًا، فأيّ برنامج Θ( n ) مثلًا هو O( n² ) وO( n ) كذلك، وإذا تخيلنا أن برنامج Θ( n ) هو عبارة عن حلقة for بسيطة تتكرر n مرة، فيمكن جعلها أسوأ بتغليفها ضمن حلقة for أخرى تتكرر n مرة أيضًا، وبالتالي ينتج برنامج له دالة f( n ) = n²، كما يمكن تعميم ذلك بالقول أنّ أي برنامج Θ( a ) هو O( b ) عندما يكون b أسوأ من a.

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

لذا يمكن القول بأن برنامجنا هو O( n² ) بطريقةٍ آمنة، وذلك لأننا حلّلنا خوارزميتنا، ووجدناها ليست أسوأ من n²، ولكنها في الواقع قد تساوي n²، وبالتالي يمكننا تقدير سرعة تشغيل برنامجنا.

لنستعرض بعض الأمثلة لتساعدك على التعرف على هذه الصيغة الجديدة.

تمرين 3

أيٌّ مما يلي صحيح؟

1. خوارزمية Θ( n ) هي O( n )
2. خوارزمية Θ( n ) هي O( n² )
3. خوارزمية Θ( n² ) هي O( n³ )
4. خوارزمية Θ( n ) هي O( 1 )
5. خوارزمية O( 1 ) هي Θ( 1 )
6. خوارزمية O( n ) هي Θ( 1 )

الحل

1. هذا صحيح لأنّ برنامجنا الأصلي كان Θ( n )، ويمكننا تحقيق O( n ) دون تغيير برنامجنا على الإطلاق.
2. هذا صحيح لأنّ n² أسوأ من n.
3. هذا صحيح لأنّ n³ أسوأ من n².
4. هذا خطأ لأنّ 1 ليس أسوأ من n، فإذا أخذ البرنامج n تعليمةً بصورةٍ مقاربة -أي عددًا خطيًا من التعليمات-، فلا يمكننا جعله أسوأ ولا يمكن جعله يأخذ تعليمةً واحدةً بصورةٍ مقاربة -أي عددًا ثابتًا من التعليمات-.
5. هذا صحيح لأنّ التعقيدان متماثلان.
6. قد يكون هذا صحيحًا أو غير صحيح وذلك اعتمادًا على الخوارزمية، لكنه خاطئ في الحالة العامة، فإذا كانت الخوارزمية Θ( 1 )، فمن المؤكد أنها O( n )؛ أما إذا كانت O( n ) فقد لا تكون Θ( 1 )، فمثلًا، خوارزمية Θ( n ) هي O ( n ) وليست Θ( 1 ).

تمرين 4

استخدم متتالية الجمع الحسابية arithmetic progression sum لإثبات أنّ البرنامج أعلاه ليس O( n² ) فقط، وإنما Θ( n² ) أيضًا، ويمكنك البحث عن معنى المتتالية الحسابية في ويكيبيديا في حالة عدم معرفتك بها.

يعطي التعقيد O-complexity لخوارزمية ما حدًا أعلى لتعقيد الخوارزمية الفعلي - أي الوقت الأكبر الذي قد تستغرقه الخوارزمية-، بينما تعطي الصيغة Θ تعقيد الخوارزمية الفعلي، حيث نقول أحيانًا أن الصيغة Θ تعطينا حدًا تامًا، وإذا علمت أننا وجدنا حد تعقيدٍ غير تام، فيمكنك استخدام الحرف الصغير o للإشارة إلى ذلك، فمثلًا، إذا كان للخوارزمية التعقيد Θ( n )، فسيكون تعقيدها التام n، وبالتالي سيكون لهذه الخوارزمية O( n ) و O( n² ) معًا.

بما أن الخوارزمية هي Θ( n )، فسيكون حد O( n ) هو الحد التام؛ أما حد O( n² ) فليس تامًا، ولذلك يمكننا كتابة أن الخوارزمية هي o( n² ) والتي تُنطق "o الصغير بالنسبة إلى مربع n"، وذلك لتوضيح أن الحد ليس تامًا.

كما يُفضَّل إيجاد حدود تامة للخوارزميات لأنها تعطينا مزيدًا من المعلومات حول سلوكها، ولكنه ليس أمرًا سهلًا دائمًا.

تمرين 5

حدّد أيًا من الحدود التالية هي حدودًا تامةً وأيها لا، ثم تحقق من صحتها أو خطئها، ويجب عليك استخدام الصيغة o لتحديد الحدود غير التامة:

1. خوارزمية Θ (n) التي لها الحد الأعلى O (n).
2. خوارزمية Θ (n²) التي لها الحد الأعلى O (n³).
3. خوارزمية Θ(1) التي لها الحد الأعلى O (n).
4. خوارزمية Θ (n) التي لها الحد الأعلى O (1).
5. خوارزمية Θ (n) التي لها الحد الأعلى O (2n).

الحل

1. الحد تام لأنّ تعقيد Θ وتعقيد O متماثلان في هذه الحالة.
2. الحد غير تام لأنّ تعقيد O أكبر من تعقيد Θ، وقد يكون حد O( n² ) تامًا، لذلك يمكننا كتابة أن الخوارزمية هي o( n³).
3. الحد غير تام، لأنّ تعقيد O أكبر من تعقيد Θ، وقد يكون حد O( 1 ) تامًا، لذلك يمكننا الإشارة بأنّ الحد O( n ) ليس تامًا من خلال كتابته بالشكل o( n ).
4. الحد خاطئ، فقد اُرتكِب خطأ في حسابه، فلا يمكن أن يكون لخوارزمية Θ( n ) حد أعلى من O( 1 )‎، وذلك لأنّ التعقيد n أكبر من التعقيد 1 -تذكر أنّ O تعطي حدًا أعلى.
5. الحد تام، فقد يبدو مثل حد غير تام، لكن هذا ليس صحيحًا في الواقع، -تذكر أنّ سلوك 2n وn المقارب هو نفسه، وأنّ الصيغتَين O وΘ تهتمان بالسلوك المقارب؛ إذًا لدينا O( 2n ) = O( n )، وبالتالي، فهذا الحد تام لأن التعقيد هو نفس Θ.

اقتباس

قاعدة عامة: يُعَدّ إيجاد تعقيد O أسهل من إيجاد تعقيد Θ لخوارزميةٍ ما.

قد تجد نفسك تائهًا قليلًا في هذه الصيغة الجديدة، ولكن سنقدم صيغتين آخرين بسيطتين بالنسبة للصيغ Θ، وO، وo قبل انتقالنا إلى بعض الأمثلة، ويُستحسَن أن تعرف هاتين الصيغتَين الآن، حيث لن نستخدمهما كثيرًا في هذا المقال لاحقًا.

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

قد تكون الصيغة Θ( n³ ) سيئًة مثل Θ (n⁴) أو أسوأ منها، لكننا نعلم أنها سيئة إلى حد ما على الأقل. إذًا تعطينا الصيغة Ω حدًا أدنى لتعقيد خوارزمية، كما يمكننا كتابة الصيغة ω على غرار الصيغة ο عندما يكون الحد ليس تامًا، فمثلًا، خوارزمية Θ ( n³ ) هي ο( n⁴ ) وω( n² ) وتُقرَأ Ω( n ) "أوميغا كبيرة بالنسبة إلى n"، بينما تُقرَأ ω( n ) "أوميغا صغيرة بالنسبة إلى n".

تمرين 6

اكتب حد O تام وآخر غير تام، وحد Ω تام وآخر غير تام من اختيارك للتعقيدات التالية، ولكن بشرط وجودهما طبعًا:

1. Θ( 1 )
2. Θ(√n)
3. Θ( n )
4. Θ( n² )
5. Θ( n³ )

الحل

هذا هو تطبيق مباشر للتعاريف أعلاه:

1. الحدود التامة هي O( 1 ) وΩ( 1 )، كما يكون حد O غير التام هو O( n ) -تذكّر أن O تعطينا حدًا أعلى-، وبما أن n أكبر من 1، فسيمثِّل حدًا غير تام يمكننا كتابته بالشكل o( n ) أيضًا، كما لا يمكننا إيجاد حد غير تام للصيغة Ω لعدم تمكننا من الحصول على أقل من 1 لهذه الدوال، إذًا يجب تعاملنا مع الحد التام فقط.
2. يجب أن تكون للحدود التامة تعقيد Θ نفسه، لذا فهي  O(√n) وΩ(√n) على التوالي؛ أما الحدود غير التامة فقد تكون O( n )، حيث تُعَدّ n أكبر من ‎√n وبالتالي فهي حد أعلى لها. وبما أننا نعلم أن هذا حدًا أعلى غير تام، فيمكننا أيضًا كتابته بالصورة o( n )؛ أما الحد الأدنى غير التام، فيمكننا ببساطة استخدام Ω( 1 )، وبما أننا نعلم أن هذا الحد ليس تامًا، فيمكننا كتابته بالصورة ω( 1. 3 ). الحدود التامة هي O( n ) وΩ( n ). قد يكون الحدان الغير تامين هما ω( 1 ) وo( n³ ) وهي في الواقع حدودٌ سيئة للغاية، لأنها بعيدة كل البعد عن التعقيدات الأصلية، إلا أنها لا تزال صالحة باستخدام التعاريف.
3. الحدود التامة هي O( n² ) وΩ( n² ) ويمكننا استخدام ω( 1 ) وo( n³ ) بالنسبة للحدود غير التامة كما في المثال السابق.
4. الحدود التامة هي O( n³ ) وΩ( n³ ) على التوالي، وقد يكون الحدان غير التامَين هما ω(‎n² √n)‎ وω(n³ √n)، وعلى الرغم من أنّ هذه الحدود ليست تامة، إلا أنها أفضل من تلك الموجودة في جواب رقم 3 و4 من هذا التمرين أعلاه.

قد تعطي الصيغتان O وΩ أيضًا حدودًا تامة، وسبب استخدامنا لهما بدلًا من الصيغة Θ هو أننا قد لا نكون قادرين على معرفة ما إذا كان الحد الذي أوجدناه تامًا أم لا، أو ربما لا نرغب في متابعة العملية باستخدام الصيغة Θ التي تحتاج تدقيقًا عميقًا.

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

لاحظ أيضًا أنه على الرغم من كون الصيغة Ω تعطينا سلوكًا ذو حدٍ منخفض للدالة -أي تحسّن برنامجنا وأصبح ينفّذ تعليماتٍ أقل-، إلا أننا ما زلنا نشير إليها بتحليل "الحالة الأسوأ"، لأننا نزوّد برنامجنا بأسوأ دخلٍ ممكن من n ونحلّل سلوكه في ظل هذا الافتراض.

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

اقتباس

قاعدة عامة: تُعَدّ جميع الرموز O، وo، وΩ، وω، وΘ مفيدةً في بعض الأحيان، لكن الرمز O هو الرمز الأكثر استخدامًا، حيث يسهُل تحديده أكثر من الرمز Θ، كما يُعَدّ أكثر فائدةً من الرمز Ω عمليًا.

اللوغاريتمات Logarithms

هل تعرف ما هي اللوغاريتمات؟ إن كانت إجابتك نعم، فلا تتردد في تخطي هذا القسم، فهذا القسم هو مقدمة لمن ليس على دراية باللوغاريتمات، أو لمن لم يستخدمها كثيرًا مؤخرًا، فهو موجَّهٌ للطلاب الأصغر سنًا، والذين لم يروا اللوغاريتمات في المدرسة بعد.

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

يوضِّح الشكل الآتي مقارنةً بين الدوال n، و‎√n، وlog( n )، إذ تنمو الدالة n -أو كما تُسمَّى الدالة الخطية linear function- المرسومة باللون الأخضر في أعلى الشكل، أسرع بكثير من دالة الجذر التربيعي المرسومة باللون الأحمر في المنتصف، والتي بدورها تنمو أسرع بكثير من الدالة log( n ) المرسومة باللون الأزرق في الجزء السفلي من هذا الرسم البياني، ويكون الفرق واضحًا تمامًا حتى بالنسبة إلى n صغيرة مثل n = 100.

تُعَدّ اللوغاريتمات عمليةً عكسيةً لرفع شيءٍ ما إلى أس مثل الجذور التربيعية التي هي عملية عكسية لتربيع شيءٍ ما، وسنشرح ذلك بمثال. ضع في بالك المعادلة التالية:

2^x = 1024

نريد حل هذه المعادلة لإيجاد قيمة x، لذلك لنسأل أنفسنا: ما هو الرقم الذي يجب رفع الأساس 2 إليه حتى نحصل على 1024؟ هذا الرقم هو 10. بالفعل لدينا ‎2¹⁰ = 1024، وهو أمر سهل التحقق منه؛ كما تساعدنا اللوغاريتمات من خلال الإشارة إلى هذه المشكلة باستخدام صيغة جديدة، فالرقم 10 في هذه الحالة هو لوغاريتم 1024 ونكتبه بالصورة ( log( 1024 ونقرأه "لوغاريتم 1024".

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

تُعَدّ لوغاريتمات الأساس 2 أكثر أنواع اللوغاريتمات شيوعًا في علوم الحاسوب لأنه غالبًا ما يكون لدينا كيانان مختلفان فقط هما: 0 و1، كما نميل أيضًا إلى تقسيم مشكلة كبيرة واحدة إلى نصفين، لذلك ما عليك سوى معرفة لوغاريتمات الأساس 2 لمتابعة هذا المقال.

تمرين 7

حُلّ المعادلات أدناه، وأوجد اللوغاريتم في كل حالة باستخدام اللوغاريتمات ذات الأساس 2 فقط:

1. 2^x = 64
2. ‎(2²)^x= 64
3. 4^x = 4
4. 2^x = 1
5. 2^x + 2^x = 32
6. ‎(2^x) * (2^x) = 64

الحل

لا يتضمن الحل أكثر من تطبيق الأفكار المُعرَّفة أعلاه:

1. يمكننا باستخدام طريقة التجربة والخطأ إيجاد أن x = 6، وبالتالي، log( 64 ) = 6.
2. يمكن كتابة ‎(2²)^x بالصورة 2^2x من خلال تطبيق خصائص الأس، إذًا لدينا 2x = 6 لأن log( 64 ) = 6 من النتيجة السابقة، وبالتالي، x = 3.
3. يمكننا كتابة 4 بالشكل 2² باستخدام معرفتنا من المعادلة السابقة، وبهذا تصبح المعادلة ‎(2²)^x= 4 وهي 2^2x = 4 نفسها، ونلاحظ أن log( 4 ) = 2 لأن ‎2² = 4، وبالتالي، لدينا أن 2x = 2، وعليه فـ x = 1؛ كما يمكن ملاحظة ذلك بسهولة من المعادلة الأصلية، حيث أن ناتج الرفع للأس 1 هو الأساس نفسه.
4. تذكر أن ناتج الرفع للأس 0 هو 1، لذلك لدينا log( 1 ) = 0، بما أنّ ‎2⁰= 1، وبالتالي، x = 0.
5. لا يمكننا أخذ اللوغاريتم مباشرةً بسبب وجود المجموع، ولكن يمكن ملاحظة أنّ 2^x+ 2^x هي ‎2 * (2^x) نفسها، حيث ضربنا هنا بالعدد 2 أي لهما الأساس نفسه، وبالتالي، ينتج 2^{x + 1}، والآن كل ما علينا فعله هو حل المعادلة 2^{x + 1}= 32، حيث نجد أنّ log( 32 ) = 5، وهكذا x + 1 = 5، وبالتالي، x = 4.
6. نضرب هنا قوتين للعدد 2 معًا، ولذلك يمكننا ضمهما من خلال ملاحظة أن (2^x) * (2^x) هي 2^2x نفسها، وبالتالي كل ما علينا فعله هو حل المعادلة 2^2x= 64 التي حللناها بالفعل أعلاه، حيث x = 3.

اقتباس

قاعدة عامة: يمكنك الحصول على تقدير تقريبي لمدى سرعة تشغيل برنامجك بمجرد تحليل التعقيد في مسابقة الخوارزميات المطبَّقة باستخدام لغة ++ C، وذلك من خلال التوقّع بأن البرنامج ينفّذ حوالي 1,000,000 عملية في الثانية، بحيث تُعطَى العمليات التي تحسب عددها من خلال دالة السلوك المقارب التي تصف خوارزميتك، وبالتالي تستغرق خوارزمية ( Θ( n مثلًا، حوالي ثانية واحدة لمعالجة الدخل من أجل n = 1,000,000.

التعقيد العودي Recursive complexity

لنلقِ نظرةً على دالة عودية recursive function، فالدالة العودية هي دالة تستدعي نفسها. هل يمكننا تحليل تعقيدها؟ توجِد الدالة الآتية والمكتوبة بلغة بايثون، حيث تُقيِّم مضروب factorial عددٍ معين، إذ يمكن إيجاد مضروب عدد صحيح موجب بضربه بجميع الأعداد الصحيحة السابقة معًا، فمثلًا، مضروب العدد 5 هو 5 * 4 * 3 * 2 * 1؛ كما نعبِّر عن ذلك بالصورة "!5" ونقرؤها "مضروب العدد خمسة five factorial"، ويفضِّل بعض الناس نُطقها بصوت عالٍ مثل "خمسة !!!".

def factorial( n ):
   if n == 1:
       return 1
   return n * factorial( n - 1 )

لنحلّل تعقيد هذه الدالة، فعلى الرغم من عدم احتواء هذه الدالة على أية حلقات، إلا أنّ تعقيدها ليس ثابتًا constant، حيث يجب علينا متابعة عد التعليمات مرةً أخرى لمعرفة تعقيدها، فإذا مرّرنا المتغير n إلى هذه الدالة، فستنفّذ n مرة؛ وإذا لم تكن متأكدًا من ذلك، فشغّل هذه الدالة "يدويًا" الآن من أجل n = 5 للتحقق منها. ستنفَّذ هذه الدالة مثلًا 5 مرات من أجل n = 5، بحيث ستستمر في إنقاص قيمة n بمقدار 1 في كل استدعاء، وبالتالي، يكون تعقيد هذه الدالة هو ( Θ( n.

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

يحتوي الشكل التالي على رسم بياني لمساعدتك على فهم مفهوم العودية المُطبَّقة عند استدعاء الدالة factorial( 5 )، ويجب على هذا الشكل توضيح لماذا تعقيد هذه الدالة هو تعقيد خطي:

العودية (معاوة الاستدعاء) التي تطبّقها الدالة factorial

التعقيد اللوغاريتمي Logarithmic complexity

إحدى المشكلات الشهيرة في علوم الحاسوب هي البحث عن قيمة داخل مصفوفة، ولقد حلّلنا هذه المشكلة سابقًا من خلال الحالة العامة، كما تصبح هذه المشكلة ممتعةً إذا كان لدينا مصفوفة مرتَّبة ونريد إيجاد قيمة معينة بداخلها، حيث تُسمَّى إحدى طرق القيام بذلك البحث الثنائي binary search.

ننظر إلى العنصر الأوسط في المصفوفة، وإذا وجدنا العنصر هناك، فقد انتهينا؛ وإلّا فإذا كانت القيمة التي وجدناها أكبر من القيمة التي نبحث عنها، فسنعلم أن العنصر سيكون في الجزء الأيسر من المصفوفة؛ وإلّا فإننا نعلم أنه سيكون في الجزء الأيمن من المصفوفة، كما يمكننا الاستمرار في تقسيم هذه المصفوفات الصغيرة إلى نصفين حتى يتبقّى عنصر واحد فقط، وتوضّح الشيفرة الوهمية التالية هذه الفكرة:

def binarySearch( A, n, value ):
   if n = 1:
       if A[ 0 ] = value:
           return true
       else:
           return false
   if value < A[ n / 2 ]:
       return binarySearch( A[ 0...( n / 2 - 1 ) ], n / 2 - 1, value )
   else if value > A[ n / 2 ]:
       return binarySearch( A[ ( n / 2 + 1 )...n ], n / 2 - 1, value )
   else:
       return true

تُعَدّ هذه الشيفرة الوهمية تبسيطًا للتطبيق الفعلي، كما يُعَدّ وصفها أسهل من تطبيقها عمليًا، حيث يحتاج المبرمج إلى الاهتمام ببعض مشاكل التطبيق.

يجب تطبيق الدالة floor()‎ أو ceil()‎ بسبب وجود أخطاء بفارق الواحد off-by-one، وقد لا ينتج عن القسمة على العدد 2 قيمةً صحيحةً، فالجزء الصحيح أو المتمم الصحيح الأسفل floor لعدد حقيقي ما x، هو أكبر عدد صحيح ليس أكبر من x، فصحيح العدد 2.6 هو 2، أي أنّ أكبر عدد صحيح ليس أكبر من 2.6. بينما السقف أو المتمم الصحيح الأعلى ceil لعدد حقيقي x، فهو أصغر عدد صحيح ولكنه ليس أصغر من x، لأن سقف العدد 2.15 هو 3، أي أنّ أصغر عدد صحيح ليس أصغر من 2.15. لكن يمكننا افتراض أن هذه الطريقة ستنجح دائمًا، وسنفترض أنّ تطبيقنا الفعلي يهتم بأخطاء الفراق الواحد off-by-one، وذلك لأننا نريد تحليل تعقيد هذه الطريقة فقط. إذا لم تطبّق البحث الثنائي مطلقًا، فقد ترغب في فعل ذلك باستخدام لغة البرمجة المفضلة لديك.

يوضّح الشكل الآتي لصاحبه لوك فرانكل Luke Francl طريقة عمل البحث الثنائي باستخدام العودية، حيث يُميَّز الوسيط A لكل استدعاء باللون الأسود، وتستمر العودية حتى تصبح المصفوفة مكوّنةً من عنصر واحد فقط.

إذا لم تكن متأكدًا من عمل هذه الطريقة، فشغّلها يدويًا باستخدام مثال بسيط واقنع نفسك بأنها تعمل بالفعل.

لنحاول تحليل هذه الخوارزمية العودية، حيث سنفترض -من أجل التبسيط- أن المصفوفة تُقسَم دائمًا إلى نصفين تمامًا، متجاهلين الجزأين 1+ و 1- من الاستدعاء العودي. كما يجب اقتناعك بعدم تأثير إجراء تغيير بسيط على نتائج التعقيد مثل تجاهل الجزأين 1+ و1-، وهذه حقيقة يجب عادةً إثباتها إذا أردنا أن نكون حريصين من وجهة نظر رياضية، لكنها بديهية عمليًا.

سنفترض للتبسيط أن حجم المصفوفة هو بالضبط قوة للعدد 2. بحيث لا يغير هذا الافتراض النتائج النهائية لتعقيدنا الذي سنصل إليه، وسيحدث السيناريو الأسوأ لهذه المشكلة عند عدم ظهور القيمة التي نبحث عنها في مصفوفتنا على الإطلاق، كما سنبدأ في هذه الحالة بمصفوفة ذات حجم n في الاستدعاء الأول للعودية، ثم سنحصل على مصفوفة بحجم n / 2 في الاستدعاء التالي. وبعدها سنحصل على مصفوفة بحجم n / 4 في الاستدعاء العودي التالي، ثم مصفوفة بحجم n / 8، وهكذا؛ حيث تقسَم المصفوفة إلى نصفين في كل استدعاء، حتى نصل إلى عنصر واحد فقط، لذلك لنكتب عدد العناصر في المصفوفة الخاصة بنا لكل استدعاء كما يلي:

0th iteration: n
1st iteration: n / 2
2nd iteration: n / 4
3rd iteration: n / 8
…
ith iteration: n / 2i
last iteration: 1

لاحظ احتواء المصفوفة على n / 2ⁱ عنصر في التكرار i بسبب تقسيم المصفوفة في كل تكرار إلى نصفين، مما يعني أننا نقسم عدد عناصرها على 2، أي نضرب المقام بـ 2؛ وإذا فعلنا ذلك i مرة، فسنحصل على n / 2ⁱ، إذ يستمر هذا الإجراء ونحصل على عدد أصغر من العناصر مع كل قيمة أكبر للمتغير i، حتى نصل إلى التكرار الأخير الذي يتبقى فيه عنصر واحد فقط، وإذا رغبنا في معرفة التكرار i الذي يتبقى فيه عنصرٌ واحد فقط، فعلينا حل المعادلة التالية:

1 = n / 2i

سيكون هذا صحيحًا فقط عندما نصل إلى الاستدعاء النهائي للدالة ()binarySearch، وليس في الحالة العامة، لذلك فإيجاد قيمة i هنا سيساعدنا في العثور على التكرار الذي ستنتهي فيه العودية. وإذا ضربنا كلا الطرفين بـ 2ⁱ فسنحصل على:

2i= n

يجب أن تبدو هذه المعادلة مألوفة إذا قرأت قسم اللوغاريتمات أعلاه، وبالتالي ينتج:

i = log( n )

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

بافتراض أنّ n = 32 فسيكون لدينا مصفوفة مؤلفة من 32 عنصرًا، فكم مرةً يجب تقسيم هذه المصفوفة إلى نصفين للحصول على عنصر واحد فقط؟ سنحتاج إلى تقسيمها خمس مرات للحصول إلى عنصر واحد، أي بالترتيب التالي: 32 ← 16 ← 8 ← 4 ← 2 ← 1، والعدد 5 هو لوغاريتم 32، لذلك يكون تعقيد البحث الثنائي هو Θ( log( n ) ).

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

اقتباس

قاعدة عامة: يؤدي تحسين وقت التشغيل المقارب لأحد البرامج، إلى تحسين أدائه بصورة أكبر من أي تحسينات "تقنية" أصغر مثل استخدام لغة برمجة أسرع.

الفرز الأمثل Optimal sorting

تهانينا! لقد بتّ الآن تعرف كلًا من تحليل تعقيد الخوارزميات، وسلوك الدوال المقارب، وصيغة big-O؛ بالإضافة إلى كيفية إيجاد تعقيد الخوارزمية ليكون O( 1 )، وO( log( n ) )، وO( n )، وO( n² ) وما إلى ذلك بديهيًا، كما أصبحت تعرف الرموز o، وO، وω، وΩ، وΘ، وماذا يعني تحليل الحالة الأسوأ أيضًا.

يُعَدّ هذا القسم الأخير من المقال أعقد قليلًا، لذا لا تتردد في أخذ راحة إذا تعبت، حيث سيتطلب منك التركيز وقضاء بعض الوقت في حل التمارين، لكنه سيوفر لك طريقةً مفيدةً للغاية في تحليل تعقيد الخوارزمية وهذا أمرٌ مهم، لذلك فهو بالتأكيد يستحق الفهم.

يُدعى الفرز الذي طبقناه سابقًا بالفرز الانتقائي، حيث ذكرنا أنه ليس الفرز الأمثل؛ والخوارزمية المثلى هي الخوارزمية التي تحل المشكلة بأفضل طريقة ممكنة، مما يعني عدم وجود خوارزميات أفضل منها، وهذا يعني أن لدى جميع الخوارزميات الأخرى الموجهة لحل المشكلة تعقيدًا أسوأً أو مساويًا لتلك الخوارزمية المثلى، كما قد يكون هناك العديد من الخوارزميات المثلى لمشكلةٍ ما بحيث تشترك جميعها في التعقيد نفسه، ويمكن حل مشكلة الفرز على النحو الأمثل بطرق مختلفة، كما يمكن استخدام فكرة البحث الثنائي نفسها من أجل الفرز بسرعة، وتسمى طريقة الفرز المثلى هذه الفرز بالدمج mergesort.

سنحتاج أولًا في إجراء فرز الدمج، إلى إنشاء دالة مساعدة والتي سنستخدمها بعد ذلك لإجراء الفرز الفعلي، حيث تأخذ دالة الدمج merge مصفوفتين مرتّبتَين سابقًا، ثم تدمجهما معًا في مصفوفة كبيرة مرتبة، ويمكن القيام بذلك بسهولة كما يلي:

def merge( A, B ):
   if empty( A ):
       return B
   if empty( B ):
       return A
   if A[ 0 ] < B[ 0 ]:
       return concat( A[ 0 ], merge( A[ 1...A_n ], B ) )
   else:
       return concat( B[ 0 ], merge( A, B[ 1...B_n ] ) )

تأخذ الدالة concat عنصرًا يُسمى "الرأس head" ومصفوفة تُسمى "الذيل tail"، ثم تبني وتعيد مصفوفةً جديدةً تحتوي على عنصر "الرأس" الذي يمثِّل العنصر الأول في المصفوفة الجديدة، وعلى عنصر "الذيل" الذي يمثِّل بقية العناصر الموجودة في المصفوفة، حيث تعيد الدالة concat( 3, [ 4, 5, 6 ] ) مثلًا، ما يلي: [ 3, 4, 5, 6 ].

ونستخدم المتغيرين An وBn للإشارة إلى أحجام المصفوفتين A وB على التوالي.

تمرين 8

تحقق من إجراء الدالة المذكورة أعلاه لعملية الدمج، ثم أعد كتابتها بلغة البرمجة المفضلة لديك بطريقة تكرارية -أي باستخدام حلقات for- بدلًا من استخدام العودية.

يكشف تحليل هذه الخوارزمية أن وقت تشغيلها Θ( n )، حيث يمثِّل n طول المصفوفة الناتجة أي n = A_n + B_n.

تمرين 9

تحقق من أن وقت تشغيل الدالة merge هو Θ( n ).

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

def mergeSort( A, n ):
   if n = 1:
       return A # it is already sorted
   middle = floor( n / 2 )
   leftHalf = A[ 1...middle ]
   rightHalf = A[ ( middle + 1 )...n ]
   return merge( mergeSort( leftHalf, middle ), mergeSort( rightHalf, n - middle ) )

يُعَدّ فهم هذه الدالة أصعب مما مررنا به سابقًا، لذلك قد يأخذ منك التمرين التالي بضع دقائق.

تمرين 10

تحقق من صحة الدالة mergeSort، وذلك من خلال التحقق من تمكّن الدالة mergeSort من فرز المصفوفة المعطاة بصورة صحيحة، وإذا واجهتك مشكلة في فهم سبب نجاحها في ذلك، فجرّبها باستخدام مصفوفة صغيرة على أساس مثال ثم شغّلها "يدويًا"، وتأكد عند تشغيل هذه الدالة يدويًا من حصولك على النصف الأيسر leftHalf والنصف الأيمن rightHalf. وإذا قسّمت المصفوفة في المنتصف تقريبًا، فليس من الضروري قسم المصفوفة في المنتصف تمامًا إذا احتوت على عدد فردي من العناصر وهذا الهدف من استخدام الدالة floor أعلاه.

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

لبهذا نكون قد قسمنا المصفوفة الأصلية إلى مصفوفتين بحجم n / 2 لكل منهما، ثم دمجنا هذه المصفوفات، وهي عملية لدمج n عنصرًا وبالتالي تستغرق وقتًا (Θ (n، كما يوضح الشكل التالي هذه العملية العودية:

شجرة العودية لطريقة الفرز بالدمج merge sort

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

يعمل الاستدعاء الأصلي للدالة mergeSort على استدعائها مرتين في مصفوفتين وحجم كل منهما n / 2، حيث يشار إلى ذلك بواسطة السهمين الموجودين في الأعلى، ثم يجري كل من هذين الاستدعائَين بدورهما استدعائين خاصين بهما لدمج مصفوفتين بحجم n / 4 لكل منهما، وهكذا دواليك حتى نصل إلى مصفوفات ذات حجم 1؛ ويسمَّى هذا الرسم البياني بالشجرة العودية recursion tree، لأنه يوضح كيفية حدوث العودية ويظهر مثل شجرة، لكن الجذر root في الأعلى والأوراق في الأسفل، لذلك يظهر مثل شجرة مقلوبة.

لاحظ أن العدد الإجمالي للعناصر هو n في كل مستوى من الرسم البياني أعلاه، حيث يحتوي المستوى الأول على استدعاء واحد فقط للدالة mergeSort مع مصفوفة بحجم n أي العدد الإجمالي للعناصر هو n، كما يحتوي المستوى الثاني على استدعائين للدالة mergeSort وكل منهما بحجم n / 2. لكن n / 2 + n / 2 = n وهكذا يكون العدد الإجمالي للعناصر هو n في هذا المستوى، كما توجد 4 استدعاءات في المستوى الثالث، بحيث يُطبَّق كل استدعاء على مصفوفة بحجم n / 4، أي سيساوي عدد العناصر الإجمالي n / 4 + n / 4 + n / 4 + n / 4 = 4n / 4 = n، وبالتالي نحصل على n عنصر.

يجب على المستدعي في كل مستوى من هذا الرسم البياني إجراء عملية دمج merge على العناصر التي يعيدها المستدعَى، إذ يجب على الدائرة المشار إليها باللون الأحمر مثلًا، ترتيب عدد n / 2 من العناصر، وذلك بتقسيم المصفوفة ذات الحجم n / 2 إلى مصفوفتين بحجم n / 4، ثم تُستدعَى الدالة mergeSort عوديًا لفرز تلك المصفوفة، ثم تُدمَجان معًا، ويُشار إلى هذه الاستدعاءات بالدوائر ذات اللون الأخضر.

تحتاج عملية الدمج إلى دمج n / 2 عنصر في كل مستوى من الشجرة، ويكون العدد الإجمالي للعناصر المدموجة هو n. حيث تدمج الدالة في ذلك المستوى n / 2 عنصر، ويجب على الدالة الموجودة على يمينها -ذات اللون الأزرق- دمج n / 2 عنصرأيضًا، وبالتالي ينتج عدد العناصر الإجمالي التي يجب دمجها في هذا المستوى .

تعقيد كل مستوى هو Θ( n )، كما يكون عدد المستويات في هذا الرسم البياني، والذي يُطلق عليه أيضًا عمق depth شجرة العودية مساويًا لـ log( n )، وسبب ذلك هو السبب ذاته تمامًا الذي استخدمناه عند تحليل تعقيد البحث الثنائي.

لدينا log( n ) مستوى وتعقيد كل مستوى هو Θ( n )، وبالتالي، يكون تعقيد الدالة mergeSort هو Θ(n * log( n ))، وهذا أفضل بكثير من Θ( n² ) الذي هو تعقيد خوارزمية الفرز الانتقائي -تذكر أنّ log( n ) أصغر بكثير من n، وبالتالي يكون n * log (n) أصغر بكثير من n * n = n²-، وإذا وجدت ذلك معقدًا، فلا تقلق لأن الأمر ليس سهلًا في المرة الأولى.

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

تُستخدَم خوارزميات الفرز التي لها وقت تشغيل Θ( n * log( n ) )عمليًا، إذ تستخدم نواة نظام لينكس مثلًا، خوارزمية فرز تسمى heapsort، والتي لها وقت تشغيل مماثل لخوارزمية الفرز بالدمج mergesort الذي أوجدناه للتو، والذي هو Θ( n log( n ) )، لذلك فهو الأمثل.

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

يجب الآن بعد قراءة هذا المقال أن يكون حدسك الذي طورته لتحليل تعقيد الخوارزمية قادرًا على مساعدتك في تصميم برامج أسرع، ويجب عليك تركيز جهودك المثلى على الأشياء المهمة حقًا بدلًا من الأشياء الصغيرة التي لا تهمك، مما يتيح لك العمل بصورةٍ أكثر إنتاجية. كما يجب أن تكون اللغة الرياضية والتمثيل الذي طُوِّر في هذا المقال مثل صيغة Big-O مفيدَين أيضًا في التواصل مع مهندسي البرمجيات الآخرين عندما تنقاشهم بموضوع وقت تشغيل الخوارزميات.

ترجمة -وبتصرف- للمقال A Gentle Introduction to Algorithm Complexity Analysis لصاحبه Dionysis "dionyziz" Zindros.

اقرأ أيضًا

• المرجع الشامل إلى تعلم الخوارزميات للمبتدئين
• تعقيد الخوارزميات Algorithms Complexity
• ترميز Big-O في الخوارزميات
• خوارزمية ديكسترا Dijkstra’s Algorithm