مدخل إلى جافا تحليل الخوارزميات في جافا

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

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

في الواقع، ليس هناك أي معنىً من تصنيف البرامج على أنها تعمل بكفاءةٍ أم لا، وإنما يكون من الأنسب أن نوازن بين برنامجين صحيحين ينفّذان نفس المهمة لنعرف أيًا منهما أكثر كفاءةً من الآخر، بمعنى أيهما ينجز مهمّته بصورةٍ أسرع، إلا أن تحديد ذلك ليس بالأمر السهل لأن زمن تشغيل البرنامج غير معرَّف؛ فقد يختلف حسب عدد معالجات الحاسوب وسرعتها، كما قد يعتمد على تصميم آلة جافا الافتراضية Java Virtual Machine (في حالة برامج جافا) المفسِّرة للبرنامج؛ وقد يعتمد كذلك على المصرّف المستخدَم لتصريف البرنامج إلى لغة الآلة، كما يعتمد زمن تشغيل أي برنامجٍ على حجم المشكلة التي ينبغي للبرنامج أن يحلّها، فمثلًا سيستغرق برنامج ترتيب sorting وقتًا أطول لترتيب 10000 عنصر مما سيستغرقه لترتيب 100 عنصر؛ وعندما نوازن بين زمنيْ تشغيل برنامجين، سنجد أن برنامج A يحلّ المشاكل الصغيرة أسرع بكثيرٍ من برنامج B بينما يحلّ البرنامج B المشاكل الكبيرة أسرع من البرنامج A، فلا يوجد برنامجٌ معينٌ هو الأسرع دائمًا في جميع الحالات.

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

يُعَد التحليل المُقارِب asymptotic analysis أحد أهم تقنيات ذلك المجال، ويُقصد بالمُقارِب asymptotic ما يميل إليه على المدى البعيد بازدياد حجم المشكلة، حيث يجيب التحليل المُقارِب لزمن تشغيل run time خوارزميةٍ عن أسئلةٍ مثل، كيف يؤثر حجم المشكلة problem size على زمن التشغيل؟ ويُعَد التحليل مُقارِبًا؛ لأنه يهتم بما سيحدث لزمن التشغيل عند زيادة حجم المشكلة بدون أي قيودٍ، أما ما سيحدث للأحجام الصغيرة من المشاكل فهي أمورٌ لا تعنيه؛ فإذا أظهر التحليل المُقارِب لخوارزمية A أنها أسرع من خوارزمية B، فلا يعني ذلك بالضرورة أن الخوارزمية A ستكون أسرع من B عندما يكون حجم المشكلة صغيرًا مثل 10 أو 1000 أو حتى 1000000، وإنما يعني أنه بزيادة حجم المشكلة، ستصل حتمًا إلى نقطةٍ تكون عندها خوارزمية A أسرع من خوارزمية B.

يرتبط مفهوم التحليل المُقارِب بـمصطلح ترميز O الكبير Big-Oh notation، حيث يمكّننا هذا الترميز من قوْل أن زمن تشغيل خوارزميةٍ معينةٍ هو O(n2)‎ أو O(n)‎ أو O(log(n))‎، وعمومًا يُشار إليه بـ O(f(n))‎، حيث f(n)‎ عِبارةٌ عن دالة تُسند عددًا حقيقيًا موجبًا لكلّ عددٍ صحيحٍ موجبٍ n، بينما يشير n ضِمن هذا الترميز إلى حجم المشكلة، ولذلك يلزَمك أن تحدّد حجم المشكلة قبل أن تبدأ في تحليلها، وهو ليس أمرًا معقدًا على أية حال؛ فمثلًا، إذا كانت المشكلة هي ترتيب قائمةٍ من العناصر، فإن حجم تلك المشكلة يمكنه أن يكون عدد العناصر ضِمن القائمة، وهذا مثالٌ آخرٌ، عندما يكون مُدخَل الخوارزمية عِبارةٌ عن عددٍ صحيحٍ (لفحْص إذا ما كان ذلك العدد عددًا أوليًا prime أم لا) يكون حجم المشكلة في تلك الحالة هو عدد البتات bits الموجودة ضِمن ذلك العدد المُدخَل لا العدد ذاته؛ وعمومًا يُعَد عدد البتات bits الموجودة في قيمة المُدخَل قياسًا جيدًا لحجم المشكلة.

إذا كان زمن تشغيل خوارزميةٍ معينةٍ هو O(f(n))‎، فذلك يعني أنه بالنسبة للقيم الكبيرة من حجم المشكلة، لن يتعدى الزمن حاصل ضرْب قيمةٍ ثابتةٍ معينةٍ في f(n)‎، أي أن هناك عدد C وعددٌ صحيحٌ آخرٌ موجبٌ M، وعندما تصبح n أكبر من M، فإن زمن تشغيل الخوارزمية يكون أقلّ من أو يساوي C×f(n)‎؛ حيث يأخذ الثابت C في حسبانه تفاصيلًا مثل سرعة الحاسوب المستخدَم في تشغيل الخوارزمية، وإذا كان ذلك الحاسوب أبطأ، فقد تستخدم قيمة أكبر للثابت، إلا أن تغييره لن يغيّر من حقيقة أن زمن تشغيل الخوارزمية هو O(f(n)‎؛ وبفضل ذلك الثابت، لن يكون من الضروري تحديد إذا ما كنا نقيس الزمن بالثواني أو السنوات أو أي وحدة قياسٍ أخرى؛ لأن التحويل من وحدةٍ معينةٍ إلى أخرى يتمثَّل بعملية ضربٍ في قيمة ثابتة، بالإضافة إلى ما سبق، لا تَعتمد O(f(n))‎ نهائيًا على ما يحدُث في الأحجام الأصغر من المشكلة، وإنما على ما يحدُث على المدى الطويل بينما يزيد حجم المشكلة دون أي قيودٍ.

سنفحص مثالًا بسيطًا عِبارةً عن حساب حاصل مجموع العناصر الموجودة ضِمن مصفوفةٍ، وفي هذه الحالة، يكون حجم المشكلة n هو طول تلك المصفوفة، فإذا كان A هو اسم المصفوفة، ستُكتب الخوارزمية بلغة جافا كالتالي:

total = 0;
for (int i = 0; i < n; i++)
   total = total + A[i];

تنفِّذ الخوارزمية عملية total = total + A[‎i]‎ عدد n من المرات، أي أن الزمن الكلي المُستغرق أثناء تلك العملية يساوي a×n، حيث a هو زمن تنفيذ العملية مرةٍ واحدةٍ؛ إلى جانب ذلك، تزيد الخوارزمية قيمة المتغيّر i وتوازنه مع قيمة n في كلّ مرةٍ تنفِّذ فيها مَتْن الحلقة loop، الأمر الذي يؤدي إلى زيادة زمن التشغيل بمقدار يساوي b×n حيث b عِبارةٌ عن ثابتٍ، وبالإضافة إلى ما سبق، يُهيئ كلًا من i وtotal إلى الصفر مبدئيًا مما يزيد من زمن التشغيل بمقدار ثابتٍ معينٍ وليكن c، وبالتالي، يساوي زمن تشغيل الخوارزمية للقيمة ‎(a+b)×n+c، حيث a وb وc عِبارةٌ عن ثوابتٍ تعتمد على عوامل مثل كيفية تصريف compile الشيفرة ونوع الحاسوب المستخدَم، وبالاعتماد على حقيقة أن c دائمًا ما تكون أقلّ من أو تساوي c×n لأي عددٍ صحيحٍ موجبٍ n، يمكننا إذًا أن نقول أن زمن التشغيل أقلّ من أو يساوي ‎(a+b+c)×n، أي أنه أقلّ من أو يساوي حاصل ضرْب ثابتٍ في n، أي يكون زمن تشغيل الخوارزمية هو O(n)‎.

إذا استشكل عليك أن تفهم ما سبق، فإنه يعني أنه لأي قيم n كبيرة، فإن الثابت c في المعادلة ‎(a+b)×n+c غير مهمٍ إذا ووزِن مع ‎(a+b)×n، ونصيغ ذلك بأن نقول إن c تعبّر عن عنصرٍ ذات رتبةٍ أقل lower order، وعادةً ما نتجاهل تلك العناصر في سياق التحليل المُقارِب؛ ويمكن لتحليلٍ مُقارِب آخرٍ أكثر حدَّة أن يستنتج ما يلي: "يَستغرق كلّ تكرار iteration ضِمن حلقة for مقدارًا ثابتًا من الوقت، ولأن الخوارزمية تتضمّن عدد n من التكرارات، فإن زمن التشغيل الكلي هو حاصل ضرْب ثابتٍ في n مضافًا إليه عناصر ذات رتبة أقلّ للتهيئة المبدئية، وإذا تجاهلنا تلك العناصر، سنجد أن زمن التشغيل يساوي O(n)‎.

اقتباس

ملحوظةٌ: عندما نقول أن زمن تشغيل خوارزميةٍ معينةٍ هو O(f(n))‎، فذلك يعني أن زمن تشغيلها لا يتعدّى حاصل ضرْب قيمةٍ ثابتةٍ معينةٍ في f(n)‎، أي تضع O(f(n))‎ حدًا أقصىً upper limit لزمن التشغيل؛ في المقابل، يمكن لزمن التشغيل أن يقلّ عن ذلك بكثير، فمثلًا إذا كان زمن تشغيل خوارزميةٍ يساوي O(n)‎، فيصحّ كذلك أن نقول أن زمن تشغيلها يساوي O( n²)‎ أو O(n¹⁰)‎، أما إذا قلّ زمن التشغيل عن حاصل ضرْب ثابتٍ في n، فسيكون أقلّ من حاصل ضرْب نفس قيمة الثابت في n² أو n¹⁰.

يفيد أحيانًا أن نخصِّص حدًا أدنىً lower limit لزمن التشغيل، حيث سيمكّننا ذلك من أن نقول أن زمن تشغيل خوارزميةٍ معينةٍ أكبر من أو يساوي حاصل ضرْب قيمةٍ ثابتةٍ في f(n)‎، وهو ما يعرّفه ترميزٌ آخرٌ هو Ω(f(n))‎، ويُقرأ أوميجا لدالة f أو ترميز أوميجا الكبير لدالة f (أوميجا Omega هو حرفٌ أبجديٌ يونانيٌ ويمثِّل الترميز Ω حالته الكبيرة)؛ وإذا شئنا الدقة، عندما نقول أن زمن تشغيل خوارزمية هو Ω(f(n))‎، فإن المقصود هو وجود عددٍ موجبٍ C وعددٍ صحيحٍ آخرٍ موجبٍ M، وعندما تكون قيمة n أكبر من M، فإن زمن تشغيل الخوارزمية يكون أكبر من أو يساوي حاصل ضرْب C في f(n)‎، ونستخلّص مما سبق أن O(f(n))‎ يوفّر معلومةً عن الحد الأقصى للزمن الذي قد تنتظره حتى تنتهي الخوارزمية من العمل، بينما يوفّر Ω(f(n))‎ معلومةً عن الحد الأدنى للزمن.

اقتباس

لاحظ أن زمن تشغيل خوارزمية حساب حاصل مجموع الأعداد ضِمن مصفوفةٍ هو نفسه أي Ω(n)‎ و O(n)‎، فعندما يتساوى زمن تشغيل خوارزميةٍ معينةٍ مع كلًا من Ω(f(n))‎ و O(f(n))‎، يُقال عندها أن زمن تشغيله هو Θ(f(n))‎، وتُقرأ ثيتا لدالة f أو ترميز ثيتا الكبير لدالة f (ثيتا هو حرفٌ أبجديٌ يونانيٌ آخرٌ)، وعندما نقول أن زمن تشغيل خوارزمية هو Θ(f(n))‎، فإن المقصود هو أن زمن التشغيل للقيم الكبيرة من n يتراوح بين a×f(n)‎ وb×f(n)‎ حيث a وb عبارةٌ عن ثوابتٍ قيمتها أكبر من صفرٍ بشرط أن تكبُر قيمة b عن a.

سنفْحص الآن خوارزميةً أخرى:

public static void simpleBubbleSort( int[] A, int n ) {
   for (int i = 0; i < n; i++) {
         // Do n passes through the array...
      for (int j = 0; j < n-1; j++) {
         if ( A[j] > A[j+1] ) {
                // A[j] و A[j+1] رتِّب
             int temp = A[j];
             A[j] = A[j+1];
             A[j+1] = temp;
         }
      }
   }
}

يمثِّل المعامِل n في المثال السابق حجم المشكلة، حيث ينفِّذ الحاسوب حلقة for الخارجية عدد n من المرات، وفي كلّ مرة ينفِّذ فيها تلك الحلقة، فإنه ينفِّذ أيضًا حلقة for داخليةً عدد n-1 من المرات، إذًا سينفّذ الحاسوب تعليمة if عدد n×(n-1)‎ من المرات، أي يساوي n²-n، ولأن العناصر ذات الرتبة الأقل غير مهمّةٍ في التحليل المُقارِب، سنكتفي بأن نقول أن تعليمة if تنفَّذ عدد n² مرةٍ؛ وعلى وجهٍ أكثر تحديدًا، ينفِّذ الحاسوب الاختبار A[j] > A[j+1] عدد n² من المرات، ويكون زمن تشغيل الخوارزمية هو Ω( n²)‎، أي يساوي حاصل ضرْب قيمةٍ ثابتةٍ في n² على الأقل، وإذا فحصنا العمليات الأخرى (تعليمات الإسناد assignment وزيادة i وj بمقدار الواحد..إلخ)، فإننا لن نجد أي عمليةً منها تنفَّذ أكثر من عدد n² مرة؛ ونستنتج من ذلك أن زمن التشغيل هو O(n2)‎ أيضًا، أي أنه لن يتجاوز حاصل ضرْب قيمةٍ ثابتةٍ في n²، ونظرًا لأن زمن التشغيل يساوي كلًا من Ω( n²)‎ و O( n²)‎، فإنه أيضًا يساوي Θ( n²)‎.

اقتباس

ملحوظة: يَستخدم البعض الترميز O(f(n))‎ كما لو كان يعني Θ(f(n))‎ أي عندما يقولون أن زمن تشغيل خوارزمية هو O(f(n))‎، فإنهم يقصدون أن زمن تشغيلها يساوي حاصل ضرْب ثابتٍ في f(n)‎ تقريبًا، وعمومًا يُفترض استخدام Θ(f(n))‎ في تلك الحالة؛ لأن O(f(n))‎ تعني على وجه الدقة أن الزمن أقلّ من حاصل ضرْب ثابتٍ في f(n)‎.

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

لكي نأخذ تلك الاعتمادية في الحسبان، سنُجري تحليلًا لزمن التشغيل على كلًا من الحالة الأسوأ the worst case analysis والحالة الوسطى average case analysis، بالنسبة لتحليل زمن تشغيل الحالة الأسوأ، سنفحص جميع المشاكل المحتملة لحجم يساوي n وسنحدّد أطول زمن تشغيل من بينها جميعًا، بالمِثل بالنسبة للحالة الوسطى، سنفحص جميع المشاكل المحتملة لحجم يساوي n ونحسب قيمة متوسط زمن تشغيلها جميعًا، وعمومًا سيَفترض تحليل زمن التشغيل للحالة الوسطى أن جميع المشاكل بحجم n لها نفس احتمالية الحدوث على الرغم من عدم واقعية ذلك في بعض الأحيان، أو حتى إمكانية حدوثه وذلك في حالة وجود عددٍ لا نهائيٍ من المشاكل المختلفة لحجمٍ معينٍ.

عادةً ما يتساوى زمن تشغيل الحالة الأسوأ والوسطى ضِمن مُضاعفٍ ثابتٍ، وذلك يعني أنهما متساويان بقدر اهتمام التحليل المُقارِب، أي أن زمن تشغيل الحالة الوسطى والحالة الأسوأ هو O(f(n))‎ أو Θ(f(n))‎، إلا أن هنالك بعض الحالات القليلة التي يختلف فيها التحليل المُقارِب للحالة الأسوأ عن الحالة الوسطى كما سنرى لاحقًا.

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

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

سنفترض أننا نوازن بين خوارزميتين لحل نفس المشكلة، وزمن تشغيل إحداها هو Θ( n²)‎ بينما زمن تشغيل الأخرى هو Θ(n³)‎، فما الذي يعنيه ذلك؟ إذا كنت تريد معرفة أي خوارزميةٍ منهما هي الأسرع لمشكلةٍ حجمها 100 مثلًا، فالأمر غير مؤكدٍ، فوِفقًا للتحليل المُقارِب يمكن أن تكون أي خوارزميةٍ منهما هي الأسرع في هذه الحالة؛ أما بالنسبة للمشاكل الأكبر حجمًا، سيصل حجم المشكلة n إلى نقطةٍ تكون معها خوارزمية Θ( n²)‎ أسرع بكثيرٍ من خوارزمية Θ(n³)‎؛ وعلاوةً على ذلك، يزداد تميز خوارزمية Θ( n²)‎ عن خوارزمية Θ(n³)‎ بزيادة حجم المشكلة أكثر فأكثر، وعمومًا ستكون هناك قيمٌ لحجم المشكلة n تكون معها خوارزمية Θ( n²)‎ أسرع ألف مرةٍ أو مليون مرةٍ أو حتى بليون مرةٍ وهكذا؛ وذلك لأن دالة a×n³ تنمو أسرع بكثيرٍ من دالة b×n² لأي ثابتين موجبين a وb، وذلك يعني أنه بالنسبة للمشاكل الكبيرة، ستكون خوارزمية Θ( n²)‎ أسرع بكثيرٍ من خوارزمية Θ(n3)‎، ونحن لا نعرف بالضبط إلى أي درجةٍ بالضبط ينبغي أن تكون المشكلة كبيرةٌ، وعمليًا، يُحتمل لخوارزمية Θ( n²)‎ أن تكون أسرع حتى للقيم الصغيرة من حجم المشكلة n؛ وعمومًا تُفضّل خوارزمية Θ( n²)‎ عن خوارزمية Θ(n³)‎.

لكي تفهم وتطبّق التحليل المُقارِب، لابدّ أن يكون لديك فكرةً عن معدّل نمو بعض الدوال الشائعة، وبالنسبة للدوال الأسية ‎(power)‎ n, n², n³, n⁴, …,، كلما كان الأس أكبر، ازداد معدّل نمو الدالة؛ أما بالنسبة للدوال الأسية exponential من النوع 2ⁿ و 10ⁿ حيث n هو الأس، يكون معدّل نموها أسرع بكثيرٍ من أي دالةٍ أسيةٍ عاديةٍ power، وعمومًا تنمو الدوال الأسية بسرعةٍ جدًا لدرجة تجعل الخوارزميات التي ينمو زمن تشغيلها بذلك المعدّل غير عمليةٍ عمومًا حتى للقيم الصغيرة من n لأن زمن التشغيل طويلٌ جدًا، وإلى جانب ذلك، تُستخدم دالة اللوغاريتم log(n)‎ بكثرةٍ في التحليل المُقارِب، فإذا كان هناك عددٌ كبيرٌ من دوال اللوغاريتم، ولكن تلك التي أساسها يساوي 2 هي الأكثر استخدامًا في علوم الحاسوب، وتُكتب عادة كالتالي log₂(n)‎، حيث تنمو دالة اللوغاريتم ببطئٍ إلى درجةٍ أبطأ من معدّل نمو n، وينبغي أن يساعدك الجدول التالي على فهم الفروق بين معدّلات النمو للدوال المختلفة:

يرجع السبب وراء استخدام log(n) بكثرةٍ إلى ارتباطها بالضرب والقسمة على 2، سنفْترض أنك بدأت بعدد n ثم قسَمته على 2 ثم قسَمته على 2 مرةٍ أخرى، وهكذا إلى أن وصَلت إلى عددٍ أقل من أو يساوي 1، سيساوي عدد مرات القسمة (مقربًا لأقرب عدد صحيح) لقيمة log(n)‎.

فمثلًا انظر إلى خوارزمية البحث الثنائي binary search في مقال البحث والترتيب في المصفوفات Array في جافا، حيث تبحث تلك الخوارزمية عن عنصرٍ ضِمن مصفوفةٍ مرتّبةٍ، وسنستخدم طول المصفوفة مثل حجمٍ للمشكلة n، إذ يُقسَم عدد عناصر المصفوفة على 2 في كلّ خطوةٍ ضِمن خوارزمية البحث الثنائي، بحيث تتوقّف عندما يصبح عدد عناصرها أقلّ من أو يساوي 1، وذلك يعني أن عدد خطوات الخوارزمية لمصفوفة طولها n يساوي log(n)‎ للحدّ الأقصى؛ ونستنتج من ذلك أن زمن تشغيل الحالة الأسوأ لخوارزمية البحث الثنائي هو Θ(log(n))‎ كما أنه هو نفسه زمن تشغيل الحالة الوسطى، في المقابل، يساوي زمن تشغيل خوارزمية البحث الخطي الذي تعرّضنا له في مقال السابق ذكره أعلاه حول البحث والترتيب في المصفوفات Array في جافا لقيمة Θ(n)‎، حيث يمنحك ترميز Θ طريقةً كميّةً quantitative لتعبّر عن حقيقة كون البحث الثنائي أسرع بكثيرٍ من البحث الخطي linear search.

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

يُعَد موضوع تحليل الخوارزميات algorithms analysis حقلًا ضخمًا ورائعًا، ناقشنا هنا جزءًا صغيرًا فقط من مفاهيمه الأساسية التي تفيد لفهم واستيعاب الاختلافات بين الخوارزميات المختلفة.

ترجمة -بتصرّف- للقسم Section 5: Analysis of Algorithms من فصل Chapter 8: Correctness, Robustness, Efficiency من كتاب Introduction to Programming Using Java.

اقرأ أيضًا

• المقال السابق: التوكيد assertion والتوصيف annotation في لغة جافا
• مدخل إلى الخوارزميات
• ترميز Big-O في الخوارزميات
• دليل شامل عن تحليل تعقيد الخوارزمية
• تعقيد الخوارزميات Algorithms Complexity
• النسخة الكاملة لكتاب مدخل إلى الذكاء الاصطناعي وتعلم الآلة