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

بعد أن تعلمنا كيفية قياس سرعة البرامج في المقال السابق قياس أداء وسرعة تنفيذ شيفرة بايثون، سنتعلم كيفية قياس الزيادات النظرية theoretical increases في وقت التنفيذ runtime مع نمو حجم البيانات الخاصة بالبرنامج، ويُطلق على ذلك في علوم الحاسوب ترميز O الكبير big O notation. ربما يشعر مطورو البرامج الذين ليس لديهم خلفية في علوم الحاسوب التقليدية بوجود نقص في معارفهم، على الرغم من كون المعرفة في علوم الحاسوب مفيدة، لكنه ليس مرتبط مباشرةً مع تطوير البرمجيات. تُعدّ Big O نوعًا من خوارزميات التحليل التي تصف تعقيد الشيفرة مع زيادة عدد العناصر التي تعمل عليها. تصنف الشيفرة في مرتبة تصف عمومًا الوقت الذي تستغرقه الشيفرة لتُنفّذ، وكلما زادت تزيد كمية العمل الواجب إنجازه. يصف مطور لغة بايثون Python نيد باتشلدر Ned Batchelder خوارزمية big O بكونها تحليلًا لكيفية "تباطؤ الشيفرة كلما زادت البيانات" وهو عنوان حديثه في معرض PyCon 2018. لننظر إلى المثال التالي: لنفترض أنه لديك كميةٌ معينةٌ من العمل الذي يستغرق ساعةً ليكتمل، فإذا تضاعفت كمية العمل، كم سيستغرق من الوقت؟ ربما تعتقد أنه سيستغرق ضعف المدة ولكن الجواب الصحيح هو: يعتمد الأمر على نوع العمل المُنجز. إذا استغرقت ساعةً لقراءة كتاب قصير، فستستغرق أكثر أو أقل من ساعتين لقراءة كتابين قصيرين، وإذا كان بإمكانك ترتيب 500 كتاب أبجديًا، سيستغرق ترتيب 1000 كتاب أكثر من ساعتين لأنك ستبحث عن المكان المناسب لكل كتاب في مجموعة أكبر من الكتب. من ناحية أخرى، إذا أردت التأكد أن رف الكتب فارغ أو لا، لا يهم إذا كان هناك 0 أو 10 أو 1000 كتاب على الرف، فنظرةٌ واحدةٌ كافية لتعرف الجواب، إذ سيبقى وقت التنفيذ على حاله بغض النظر عن عدد الكتب الموجودة. يمكن أن يكون بعض الناس أسرع أو أبطأ في قراءة أو ترتيب الكتب أبجديًا ولكن تبقى هذه التوجهات العامة نفسها. تصف خوارزمية big O هذه التوجهات، إذ يمكن أن تُنفذ الخوارزمية على حاسوب سريع أو بطيء ولكننا نستطيع استخدام big O لوصف كيفية عمل الخوارزمية عمومًا، بغض النظر عن العتاد الذي ينفذ هذه الخوارزمية. لا تستخدم big O وحدات معينة مثل الثواني أو دورات المعالج لوصف وقت تنفيذ الخوارزمية لأنها تختلف بين أجهزة الحاسوب ولغات البرمجة. مراتب Big O يُعرّف ترميز Big O عادةً المراتب التالية، التي تتراوح من المنخفضة -التي تصف الشيفرة التي لا تتباطأ كثيرًا كلما زادت البيانات- إلى المراتب العليا -التي تصف الشيفرة الأكثر تباطؤًا: O(1)‎ وقت ثابت (أدنى مرتبة) O(log n)‎ وقت لوغاريتمي O(n)‎ وقت خطي O(n log n)‎ وقت N-Log-N O(n2)‎ وقت متعدد الحدود O(2n)‎ وقت أسي O(n!)‎ وقت عاملي (أعلى مرتبة) لاحظ أن big O تستخدم حرف O كبير متبوعًا بقوسين يحتويان وصف المرتبة، إذ يمثّل حرف O الكبير المرتبة وتمثل n حجم دخل البيانات التي تعمل عليها الشيفرة. نلفظها "big oh of n" أو "big oh n". لا تحتاج لفهم المعنى الدقيق لكلمات مثل لوغاريتمي أو حدودي لاستخدام صيغة big O، إذ سنصِف كل نوع بالتفصيل في الفقرة التالية ولكن هذا تبسيط لهم: خوارزميات O(1)‎ و O(log n)‎ سريعة خوارزميات O(n)‎ و O(n log n)‎ ليست سيئة خوارزميات O(n2)‎ و O(2n)‎ بطيئة يمكن طبعًا مناقشة العكس في بعض الحالات ولكن هذه التوصيفات هي قواعد جيدة عمومًا، فهناك مراتب أكثر من big O المذكورة هنا ولكن هذه هي الأعم. دعنا نتحدث عن أنواع المهام التي يصفها كل نوع من هذه المهام. اصطلاح رف الكتب Bookshelf لمراتب Big O سنستمر في المثال التالي لمراتب big O باستخدام مصطلح رف الكتب، إذ تمثّل n عدد الكتب في الرف ويصف ترميز Big O كيف أن المهام المختلفة تستغرق وقتًا أطول كلما زاد عدد الكتب. تعقيد O(1)‎: وقت ثابت معرفة "هل رف الكتب فارغ؟" هي عملية ذات وقت ثابت، إذ لا يهم عدد الكتب في الرف، فنظرةٌ واحدةٌ ستخبرنا ما إذا كان رف الكتب فارغ أم لا. يمكن أن يختلف عدد الكتب ولكن وقت التنفيذ يبقى ثابتًا، لأنه طالما رأينا كتابًا واحدًا على الرف يمكننا إيقاف البحث. القيمة n غير مهمة لسرعة تنفيذ المهمة لذا لا يوجد n في O(1)‎. يمكنك أيضًا رؤية الوقت الثابت مكتوبًا (O(c أحيانًا ‎. تعقيد O(log n)‎: لوغاريتمي اللوغاريتم هو عكس الأس، الأس 24 أو 2×2×2×2 يساوي 16 ولكن اللوغاريتم log2(16)‎ (تلفظ لوغاريتم أساس 2 للعدد 16) يساوي 4. نفترض في البرمجة قيمة الأساس 2 ولذلك نكتب O(log n)‎ بدلًا من O(log2 n)‎. البحث عن كتاب في رف كتب مرتب أبجديًا هي عملية لوغاريتمية الوقت؛ فمن أجل إيجاد كتاب واحد، يمكن التحقق من الكتاب في منتصف الرف، وإذا كان هو الكتاب المطلوب تكون قد انتهيت، وإذا لم يكن كذلك، يمكن تحديد إذا كان الكتاب قبل أو بعد الكتاب الذي في المنتصف. يقلل ذلك مجال البحث إلى النصف، ويمكنك تكرار هذه العملية مجددًا من خلال فحص الكتاب الذي في منتصف النصف الذي تتوقع فيه إيجاد الكتاب. نسمي ذلك خوارزمية بحث ثنائية binary search وهناك مثال على ذلك في "أمثلة عن ترميز Big O" لاحقًا. عدد المرات التي تستطيع قسم مجموعة n كتاب للنصف هي log2 n، في رف فيه 16 كتاب ستحتاج إلى 4 خطوات على الأكثر لإيجاد الكتاب الصحيح، لأن كل خطوة تقلل عدد الكتب التي يجب البحث فيها إلى النصف. يحتاج رف الكتب الذي فيه ضعف عدد الكتب فقط إلى خطوة إضافية واحدة للبحث عنه. إذا كان هناك 4.2 مليار كتاب في رف كتب مرتبة أبجديًا ستحتاج فقط إلى 32 خطوة لإيجاد كتاب معين. تتضمن خوارزميات Log n عادةً خطوة فرّق تسد divide and conquer وتنطوي على اختيار نصف دخل n للعمل عليه وبعدها نصف آخر من ذلك النصف وهكذا دواليك. تتدرج عمليات log n جيدًا، إذ يمكن أن يزداد العمل n إلى الضعف ولكن سيزداد وقت التنفيذ خطوةً واحدةً فقط. تعقيد O(n)‎: وقت خطي تستغرق عملية قراءة كل الكتب على الرف وقتًا خطيًا؛ فإذا كانت الكتب بنفس الطول تقريبًا وضاعفت عدد الكتب على الرف، فسيستغرق ضعف الوقت تقريبًا لقراءة كل الكتب، ويزداد وقت التنفيذ بالتناسب مع عدد الكتب n. تعقيد O(n log n)‎: وقت N-Log-N ترتيب الكتب أبجديًا هي عملية تستغرق وقت n-log-n. هذه المرتبة هي ناتج ضرب وقتي التنفيذ O(n)‎ و O(log n)‎ ببعضهما. يمكن القول أن مهمة O(n log n)‎ هي مهمة O(log n)‎ مع تنفيذها n مرة. فيما يلي تفسير بسيط حول ذلك. ابدأ بمجموعة كتب يجب ترتيبها أبجديًا ورف كتب فارغ، واتبع الخطوات في خوارزمية البحث الثنائي كما موضح في الفقرة السابقة "تعقيد O(log n)‎: زمن لوغاريتمي" لمعرفة مكان كل كتاب على الرف. هذه عملية O(log n)‎، ومن أجل ترتيب n كتاب أبجديًا وكان كل كتاب بحاجة إلى log n خطوة لترتيبه أبجديًا، ستحتاج n×log n أو n log n خطوة لترتيب كل مجموعة الكتب أبجديًا. إذا تضاعف عدد الكتب سيستغرق أكثر من ضعف الوقت لترتيبهم أبجديًا، لذا تتدرج خوارزميات n log n جيدًا. خوارزميات الترتيب ذات الكفاءة، هي: O(n log n)‎، مثل ترتيب الدمج merge sort والترتيب السريع quicksort وترتيب الكومة heapsort وترتيب تيم Timsort (من اختراع تيم بيترز Tim Peters وهي الخوارزمية التي يستخدمها تابع sort()‎ الخاص ببايثون). تعقيد O(n2)‎: وقت متعدد الحدود التحقق من الكتب المكررة في رف كتب غير مرتب هي عملية تستغرق وقت حدودي polynomial time operation؛ فإذا كان هناك 100 كتاب يمكنك أن تبدأ بالكتاب الأول وتقارنه مع التسعة وتسعون الكتاب الباقين لمعرفة التشابه، ثم نأخذ ثاني كتاب ونتحقق بنفس الطريقة مثل باقي بقية الكتب التسعة وتسعون. خطوات التحقق من التكرار لكتاب واحد هي 99 (سنقرّب هذا الرقم إلى 100 الذي هو n في هذا المثال). يجب علينا فعل ذلك 100 مرة، مرةً لكل كتاب، لذا عدد خطوات التحقق لكل كتاب على الرف هو تقريبًا n×n أو n2. (يبقى هذا التقريب n2 صالحًا حتى لو كنا أذكياء ولم نكرر المقارنات). يزداد وقت التنفيذ بازدياد عدد الكتب تربيعيًا. سيأخذ التحقق من التكرار لمئة كتاب 100×100 أو 10,000 خطوة، ولكن التحقق من ضعف هذه القيمة أي 200 كتاب سيكون 200×200 أو 40,000 خطوة، أي أربع مرات عمل أكثر. وجد بعض الخبراء في كتابة الشيفرات الواقعية للعالم الحقيقي أن معظم استخدامات تحليل big O هي لتفادي كتابة خوارزمية O(n2)‎ عن طريق الخطأ، عند وجود خوارزمية O(n log n)‎ أو O(n)‎. مرتبة O(n2)‎ هي عندما تبدأ الخوارزميات بالتباطؤ كثيرًا، لذا معرفة أن الشيفرة الخاصة بك في مرتبة O(n2)‎ أو أعلى يجب أن يجعلك تتوقف. ربما توجد خوارزمية مختلفة يمكنها حل المشكلة بصورةٍ أسرع، ويمكن في هذه الحالة أن يكون الإطلاع على قسم هيكلة البيانات والخوارزميات Data Structure and Algorithms -أو اختصارًا DSA- إما على أكاديمية حسوب مفيدًا. نسمي أيضًا O(n2)‎ وقتًا تربيعيًا، ويمكن أن يكون لخوارزميات O(n3) وقتًا تكعيبيًا وهو أبطأ من O(n2)‎ أو وقتًا رباعيًا O(n4)‎ الذي هو أبطأ من O(n3)‎ أو غيره من الأوقات الزمنية متعددة الحدود. تعقيد O(2n): وقت أسي أخذ صور لرف الكتب مع كل مجموعة ممكنة من الكتب هو عملية تستغرق وقتًا أُسّيًا. انظر لهذا الأمر بهذه الطريقة، كل كتاب على الرف يمكن أن يكون في الصورة أو لا يكون. يبين الشكل 1 كل مجموعة ممكنة، إذ تكون n هي 1 أو 2 أو 3. إذا كانت n هي 1 هناك طريقين للتجميع، إذا كانت n هي 2 هناك أربعة صور ممكنة، الكتابان على الرف، أو الكتابان ليسا على الرف، أو الكتاب الأول موجود والثاني ليس موجودًا، أو الكتاب الأول ليس موجودًا والثاني موجود. إذا أضفنا كتابًا ثالثًا، نكون قد ضاعفنا مرةً ثانية العمل المُراد فعله، لذا يجب عليك النظر إلى كل مجموعة فرعية لكتابين التي تضم الكتاب الثالث (أربعة صور) وكل مجموعة فرعية لكتابين دون الكتاب الثالث (أربعة صور أُخرى أي 23 أو 8 صور). يضاعف كل كتاب إضافي كمية العمل، فمن أجل n كتاب سيكون عدد الصور التي يجب أخذها (أي العمل الواجب فعله) هو 2n. [الشكل 1: مجموعة الكتب الممكنة على رف كتب من أجل كتاب واحد أو اثنين أو ثلاث كتب] يزداد وقت التنفيذ للمهام الأُسية بسرعة كبيرة. تحتاج ستة كتب إلى 26 أو 32 صورة، ولكن 32 كتاب يحتاج 232 أو أكثر من 4.2 مليار صورة. مرتبة O(22) أو O(23)‎ أو O(24) وما بعدها هي مراتب مختلفة ولكنها كلها تحتوي تعقيدات وقت أُسّي. تعقيد O(n!)‎: وقت عاملي أخذ صورةٍ لكل ترتيب معين هي عملية تستغرق وقتًا عاملي. نطلق على كل ترتيب ممكن اسم التبديل permutation من أجل n كتاب. النتيجة هي ترتيب n!‎ أو n عاملي، فمثلًا 3‎!‎‎ هي 3×2×1 أو 6. يبين الشكل 2 كل التبديلات الممكنة لثلاثة كتب. [الشكل 2: كل تبديلات !3 (أي 6) لثلاثة كتب على رف كتب] لحساب ذلك بنفسك، فكر بكل التبديلات الممكنة بالنسبة إلى n كتاب. لديك n خيار ممكن للكتاب الأول وبعدها n-1 خيار ممكن للكتاب الثاني (أي كل كتاب ما عدا المكان الذي اخترته للكتاب الأول) وبعدها n-2 خيار ممكن للكتاب الثالث وهكذا دواليك. مع 6 كتب تكون نتيجة !6 هي 6×5×4×3×2×1 أو 720 صورة. إضافة كتاب واحد آخر يجعل عدد الصور المطلوبة !7 أو 5.040. حتى من أجل قيم n صغيرة، تصبح خوارزميات الوقت العاملي مستحيلة الإنجاز في وقت منطقي، فإذا كان لديك 20 كتاب ويمكنك ترتيبهم وأخذ صورة كل ثانية، فستحتاج إلى وقت أكثر من عمر الكون للانتهاء من كل تبديل. واحدة من مشاكل O(n!)‎ المعروفة هي معضلة مندوب المبيعات المسافر، إذ يجب على مندوب المبيعات أن يزور n مدينة ويريد حساب المسافة المقطوعة لكل مراتب n!‎ الممكنة والتي يمكنه زيارتها، إذ يستطيع من تلك الحالات إيجاد أقصر طريق، ومن أجل منطقة بعدد كبير من المدن تصبح هذه المهمة مستحيلة الإنجاز في وقت منطقي. لحسن الحظ هناك خوارزميات مُحسنة لإيجاد طريق قصير (ولكن ليس من المضمون أن يكون الأقصر) بطريقة أسرع من O(n!)‎. يحسب ترميز Big O الحالات الأسوأ يحسب Big O أسوأ حالة ممكنة لأي مهمة، إذ يحتاج إيجاد كتاب معين في رف كتب غير مُنظم مثلًا أن تبدأ من أحد الأطراف وتتحقق من الكتب حتى تجد الكتاب المطلوب. يمكن أن تكون محظوظًا ويكون الكتاب المطلوب هو أول كتاب تتحقق منه، ولكن ربما تكون سيء الحظ ويكون الكتاب الذي تريده هو آخر كتاب تتحقق منه، أو قد لا يكون موجودًا على الرف إطلاقًا. لذلك، في أفضل الحالات لا يهم إذا كان هناك مليارات الكتب التي يجب البحث فيها لأنك ستجد الكتاب الذي تريده مباشرةً، لكن هذا التفاؤل ليس مفيدًا في خوارزميات التحليل. تصف Big O ماذا يحصل في الحالات الأسوأ حظًا، أي إذا كان لديك n كتاب يجب عليك البحث في كل الكتب، ففي هذا المثال يزداد وقت التنفيذ بنفس معدل ازدياد عدد الكتب. يستخدم بعض المبرمجين ترميز big Omega لوصف الحالة الأفضل للخوارزمية، فمثلًا تعمل خوارزمية ‎Ω(n)‎ بكفاءة خطية في أفضل حالاتها وفي الحالة الأسوأ ربما تستغرق وقتًا أطول. تواجه بعض الخوارزميات حالات محظوظة جدًا، يحيث لا تعمل أي شيء، مثل إيجاد مسار الطريق لمكان أنت أصلًا فيه. يصف ترميز Big Theta الخوارزميات التي لها الترتيب نفسه في أسوأ وأفضل الحالات، فمثلًا تصف ‎Θ(n)‎ خوارزميةً لديها كفاءة خطية في أحسن وأسوأ الحالات، أي أنها خوارزمية O(n)‎ وكذلك ‎Ω(n)‎. لا يُستخدم هذين الترميزين كثيرًا مثل استخدام big O ولكن تجدر معرفتهما. يُعد سماع الناس يتحدثون عن "big O الحالة الوسطية" عندما يعنون big Theta أو "big O الحالة الفُضلى" عندما يعنون big Omega أمرًا شائعًا رغم أنه متناقض؛ إذ تصف big O الحالة الأسوأ لوقت تنفيذ الخوارزمية تحديدًا، ولكن حتى لو كانت كلماتهم خاطئة لا تزال تفهم المعنى بغض النظر. العمليات الرياضية الكافية للتعامل مع Big O إذا كان علم الجبر لديك ضعيفًا فمعرفة العمليات الرياضية التالية أكثر من كافي عند التعامل مع big O: الضرب: تكرار الإضافة أي 2×4=8 هو مثل 2+2+2+2=8، وفي حال المتغيرات يكون n+n+n هو 3‎×n. ترميز الضرب: يهمل ترميز الجبر عادةً إشارة ×، لذا 2‎×n تُكتب 2n ومع الأرقام 3×2 تُكتب (3)2 أو ببساطة 6. خاصية الضرب بالعدد 1: ضرب أي عدد بالرقم 1 يُنتج الرقم نفسه أي 5=x1‏5 و42 =x1‏42 أو عمومًا n×1=n توزيع الضرب على الجمع: (3×2) + (3×2) = (4+3)2x كل طرف من المعادلة يساوي 14 أي عمومًا a(b+c) = ab+ac الأس: تكرار الضرب 16= 24 (تُلفظ "2 مرفوعة للقوة الرابعة تساوي 16") مثل 2×2×2×2= 16 هنا تكون 2 هي الأساس و 4 هي الأس. باستخدام المتغيرات n×n×n×n هي n4. يُستخدم في بايثون المعامل ** على سبيل المثال 2**4 تساوي 16. الأس الأول يساوي الأساس: 2= 21 و 9999=99991 وبصورةٍ عامة n1=n الأس 0 يساوي 1: 1= 20 و 1=99990 وبصورةٍ عامة n0=1 المعاملات: عوامل الضرب في 3n2+4n+5 المعاملات هي 3 و4 و5. يمكنك معرفة أن 5 هي معامل لأن 5 يمكن أن يُعاد كتابتها بالشكل (1)5 وأيضًا يمكن إعادة كتابتها 5n0. اللوغاريتمات: عكس الأس. لأن 16=24 نعرف أن log2(16)=4. نفول لوغاريتم الأساس 2 للعدد 16 هو 4. نستخدم في بايثون دالة math.log()‎ إذ math.log(16, 2)‎ تساوي إلى 4.0. يتطلب حساب big O تبسيط العمليات عن طريق جمع الحدود المتشابهة؛ والحد هو مجموعة من الأرقام والمتغيرات مضروبة مع بعضها، ففي 3n2+4n+5 تكون الحدود هي 3n2 و4n و5، إذ أن الحدود المتشابهة لديها نفس المتغير مرفوعًا لنفس القوة. في التعبير 3n2+4n+6n+5 الحدان 4n و6n هما متشابهان بإمكاننا التبسيط وإعادة الكتابة كالتالي 3n2+10n+5. خذ بالحسبان أنه يمكن كتابة 3n2+5n+4 على النحو التالي 3n2+5n+4(1)‎، إذ تطابق الحدود في هذا التعبير مرتبات big O التالية O(n2)‎ و O(n)‎ و O(1)‎. سيفيد هذا لاحقًا عندما نُسقط المعاملات في حسابات big O. ستفيد هذه التذكرة عندما تحاول معرفة big O لقطعة من الشيفرة، ولكن لن تحتاجها بعد أن تنتهي من "تحليل Big O بنظرة سريعة" في المقال التالي. مفهوم big O بسيط ويمكن أن يفيد حتى لو لم تتبع القواعد الرياضية بصرامة. الخلاصة يُعد ترميز Big O من أكثر المفاهيم انتشارًا في علم الحواسيب للمبرمجين، وهو بحاجة لبعض المفاهيم في الرياضيات لفهمه، ولكن يمكن للمفهوم الأساسي، ألا وهو معرفة أن الشيفرة ستبطأ كلما زادت البيانات، أن يصف الخوارزميات دون الحاجة إلى أرقام كبيرة لحسابها. هناك سبع مراتب لترميز big O، وهي: O(1)‎ أو الوقت الثابت، الذي يصف الشيفرة التي لا تتغير مع زيادة البيانات؛ و O(log n)‎ أو الوقت اللوغاريتمي الذي يصف الشيفرة التي تزداد بخطوة كلما تضاعف عدد البيانات بمقدار n؛ و O(n)‎ أو الوقت الخطي، الذي يصف الشيفرة التي تتباطأ يتناسب مع زيادة حجم البيانات بمقدار n؛ و O(n log n)‎ أو وقت n-log-n، الذي يصف الشيفرة التي هي أبطأ من O(n)‎ والعديد من خوارزميات الترتيب لديها هذه المرتبة. المراتب الأعلى هي أبطأ لأن وقت تنفيذها يزداد بصورةٍ أسرع من زيادة حجم دخل البيانات. يصف الوقت الحدودي O(n2)‎ الشيفرة التي يزداد وقت تنفيذها بتربيع الدخل n. ليست المراتب O(2n)‎ أو الوقت الأسّي، و O(n!)‎ أو الوقت العاملي شائعة جدًا، ولكنها تأتي مع المجموعات والتبديلات على الترتيب. ترجمة -وبتصرف- لقسم من الفصل Measuring Performance And Big O Algorithm Analysis من كتاب Beyond the Basic Stuff with Python. اقرأ أيضًا المقال السابق: قياس أداء وسرعة تنفيذ شيفرة بايثون -تحليل الخوارزميات تعقيد الخوارزميات Algorithms Complexity دليل شامل عن تحليل تعقيد الخوارزمية

لا يملك الكثير من المبرمجين الذين يصنعون أروع البرامج وأكثرها فائدةً اليوم -مثل العديد من الأشياء التي نراها على الإنترنت أو نستخدمها يوميًا- خلفيةً نظريةً في علوم الحاسوب، لكنهم لا يزالون مبرمجين رائعين ومبدعين ونقدِّر ما يبنونه، حيث تملك علوم الحاسوب النظرية استخداماتها وتطبيقاتها، ويمكن أن تكون عمليةً تمامًا. يستهدف هذا المقال المبرمجين الذين يعرفون عملهم جيدًا ولكنهم لا يملكون خلفيةً نظريةً في علوم الحاسوب، وذلك من خلال واحدة من أكثر أدوات علوم الحاسوب واقعيةً، وهي: صيغة 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 يميل إلى اللانهاية؛ ولكن إن لم تفهم ما تعنيه هذه العبارة، فلا تقلق لأنّ هذا كل ما تحتاج إلى معرفته، كما لن نستطيع إهمال الثوابت في النهاية في إطار رياضي صارم، ولكننا نفعل ذلك لأغراض علوم الحاسوب وللأسباب الموضَّحة أعلاه. سنحل بعض الأمثلة لفهم الفكرة أكثر، فمثلًا، لنجد السلوك المقارب لدوال المثال التالي بإهمال العوامِل الثابتة، والحفاظ على الأقسام التي تكبر بسرعة: تعطي الدالة f( n ) = 5n + 12 الدالة f( n ) = n باستخدام الاستنتاج نفسه بالضبط كما هو مذكور أعلاه. تعطي الدالة f (n) = 109 الدالة f( n ) = 1، حيث سنهمل معامل الضرب 109 * 1، لكن لا يزال يتعين علينا وضع 1 هنا للإشارة إلى أنّ لهذه الدالة قيمة غير صفرية. تعطي الدالة f( n ) =n2 + 3n + 112 الدالة f( n ) = n2، حيث تكبرn2 أكثر من 3n بالنسبة لقيمة n كبيرة بدرجة كافية، لذلك نحتفظ بها. تعطي الدالة f( n ) = n3 + 1999n + 1337 الدالة f( n ) = n3، فعلى الرغم من أنّ العامل الموجود أمام n كبير جدًا، لكن لا يزال بإمكاننا العثور على قيمة n كبيرة بما يكفي، بحيث يكون n3 أكبر من 1999n، وبما أننا مهتمون بسلوك قيم n الكبيرة جدًا، فسنبقي على n3 فقط، أي تصبح الدالة n3 المرسومة باللون الأزرق في الشكل التالي أكبر من الدالة 1999n المرسومة باللون الأحمر بعد القيمة n = 45، كما تبقى هي الأكبر بعد هذه النقطة إلى الأبد. تعطي الدالة f( n ) = n +√n الدالة f (n) = n، وذلك لأنّ n تنمو أسرع من ‎√n كلما زادتn ويمكنك تجربة الأمثلة الآتية بنفسك. تمرين 1 f( n ) = n6 + 3n f( n ) = 2n + 12 f( n ) = 3n + 2n f( n ) = nn + 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 ) = n2. إذا استدعى برنامج دالةً داخل حلقة وعرفنا عدد التعليمات التي تجريها الدالة المستدعاة، فمن السهل تحديد عدد تعليمات البرنامج بأكمله. لنلقِ نظرةً على المثال التالي المكتوب بلغة ? int i; for ( i = 0; i < n; ++i ) { f( n ); } إذا علمنا أن f( n ) هي دالة تنفِّذ n تعليمة بالضبط، فيمكننا حينئذٍ معرفة أن عدد تعليمات البرنامج بأكمله هو n2 بصورةٍ مقاربة، حيث تُستدعى الدالة n مرة تمامًا. ننتقل الآن إلى الصيغة التخيُّلية التي يستخدمها علماء الحاسوب للسلوك المقارب، حيث سنقول أن برنامجنا هو Θ ( f( n )) عندما نحدِّد الدالة f بصورة مقاربة، فمثلًا، البرامج المذكورة أعلاه هي Θ (1) وΘ( n2 ) وΘ( n2 ) على التوالي، حيث تُقرَأ Θ( n ) "ثيتا بالنسبة إلى n". نقول أحيانًا أنّ f( n ) -وهي الدالة الأصلية التي تحسب عدد التعليمات بما في ذلك الثوابت- هي شيء ما Θ، حيث نقول مثلًا أنّ f( n ) = 2n هي دالة Θ( n )، كما يمكننا كتابة 2n ∈ Θ (n)‎ أيضًا، والتي تُنطَق "2n هي ثيتا بالنسبة إلى n". لا ترتبك بشأن هذا الصيغة، فكل ما تنص عليه هو أنه إذا حسبنا عدد التعليمات التي يحتاجها البرنامج وهي 2n، فسيُوصَف السلوك المقارب للخوارزمية بـ n والذي نتج بإهمال الثوابت. فيما يلي بعض العبارات الرياضية الصحيحة باستخدام هذا الصيغة: n6 + 3n ∈ Θ( n6 ) 2n + 12 ∈ Θ( 2n ) 3n + 2n ∈ Θ( 3n ) nn + n ∈ Θ( nn ) بالمناسبة، إذا حللت التمرين 1 السابق، فهذه هي بالضبط الإجابات التي يجب أن تصل إليها. نسمّي ما نضعه ( هنا )Θ التعقيد الزمني time complexity، أو تعقيد complexity الخوارزمية، لذلك فللخوارزمية التي تحتوي على الصيغة Θ( n ) تعقيدٌ هو n. لدينا أيضًا أسماءً خاصةً للصيغ التالية: Θ( 1 )، وΘ( n )، وΘ( n2 ) وΘ( log( n ) )، وذلك لكثرة ظهورها، حيث نقول أنّ خوارزمية Θ( 1 ) هي خوارزمية ذات وقت ثابت constant-time algorithm، والخوارزمية Θ( n ) خطية linear، وΘ( n2 ) تربيعية 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 مرة دائمًا بدلًا من تكرارها عددًا متغيرًا من المرات، كما ستكون بعض هذه التكرارات عديمة الفائدة، لكنها ستساعدنا في تحليل تعقيد الخوارزمية الناتجة؛ وإذا أجرينا هذا التغيير البسيط، فمن الواضح أن الخوارزمية الجديدة التي أنشأناها هي Θ( n2 ) وذلك لوجود حلقتين متداخلتين بحيث يتكرر كل منهما n مرة بالضبط، وبالتالي، يمكننا القول أنّ الخوارزمية الأصلية هي O( n2 ). تُنطَق O( n2 ) "أوه كبيرة لمربع n، أي big oh of n squared"، وهذا يقودنا للقول بأن برنامجنا ليس أسوأ من n2 بصورةٍ مقاربة، فقد يكون أفضل من ذلك أو مثله. إذا كان برنامجنا هو بالفعل Θ( n2 ) فلا يزال بإمكاننا القول أنه O( n2 ) أي تخيل تغيير البرنامج الأصلي بطريقة لا تغيره كثيرًا، لكنها لا تزال تجعله أسوأ قليلًا مثل إضافة تعليمات لا معنى لها في بداية البرنامج، بحيث سيؤدي فعل ذلك إلى تغيير دالة عدّ التعليمات بواسطة ثابت بسيط، والذي سنتجاهله عندما يتعلق الأمر بالسلوك المقارب، وبالتالي فالبرنامج Θ( n2 ) هو O( n2 ) أيضًا. قد لايكون البرنامج O( n2 ) هو Θ( n2 ) أيضًا، فأيّ برنامج Θ( n ) مثلًا هو O( n2 ) وO( n ) كذلك، وإذا تخيلنا أن برنامج Θ( n ) هو عبارة عن حلقة for بسيطة تتكرر n مرة، فيمكن جعلها أسوأ بتغليفها ضمن حلقة for أخرى تتكرر n مرة أيضًا، وبالتالي ينتج برنامج له دالة f( n ) = n2، كما يمكن تعميم ذلك بالقول أنّ أي برنامج Θ( a ) هو O( b ) عندما يكون b أسوأ من a. لا يحتاج التغيير الذي أجريناه على البرنامج إلى إعطائنا برنامجًا له معنى أو مكافئًا لبرنامجنا الأصلي، حيث يحتاج فقط إلى تنفيذ تعليمات أكثر من التعليمات الأصلية بالنسبة إلى قيمة n معينة، أي نستخدم هذا التغيير من أجل حساب عدد التعليمات فقط وليس لحل مشكلتنا. لذا يمكن القول بأن برنامجنا هو O( n2 ) بطريقةٍ آمنة، وذلك لأننا حلّلنا خوارزميتنا، ووجدناها ليست أسوأ من n2، ولكنها في الواقع قد تساوي n2، وبالتالي يمكننا تقدير سرعة تشغيل برنامجنا. لنستعرض بعض الأمثلة لتساعدك على التعرف على هذه الصيغة الجديدة. تمرين 3 أيٌّ مما يلي صحيح؟ خوارزمية Θ( n ) هي O( n ) خوارزمية Θ( n ) هي O( n2 ) خوارزمية Θ( n2 ) هي O( n3 ) خوارزمية Θ( n ) هي O( 1 ) خوارزمية O( 1 ) هي Θ( 1 ) خوارزمية O( n ) هي Θ( 1 ) الحل هذا صحيح لأنّ برنامجنا الأصلي كان Θ( n )، ويمكننا تحقيق O( n ) دون تغيير برنامجنا على الإطلاق. هذا صحيح لأنّ n2 أسوأ من n. هذا صحيح لأنّ n3 أسوأ من n2. هذا خطأ لأنّ 1 ليس أسوأ من n، فإذا أخذ البرنامج n تعليمةً بصورةٍ مقاربة -أي عددًا خطيًا من التعليمات-، فلا يمكننا جعله أسوأ ولا يمكن جعله يأخذ تعليمةً واحدةً بصورةٍ مقاربة -أي عددًا ثابتًا من التعليمات-. هذا صحيح لأنّ التعقيدان متماثلان. قد يكون هذا صحيحًا أو غير صحيح وذلك اعتمادًا على الخوارزمية، لكنه خاطئ في الحالة العامة، فإذا كانت الخوارزمية Θ( 1 )، فمن المؤكد أنها O( n )؛ أما إذا كانت O( n ) فقد لا تكون Θ( 1 )، فمثلًا، خوارزمية Θ( n ) هي O ( n ) وليست Θ( 1 ). تمرين 4 استخدم متتالية الجمع الحسابية arithmetic progression sum لإثبات أنّ البرنامج أعلاه ليس O( n2 ) فقط، وإنما Θ( n2 ) أيضًا، ويمكنك البحث عن معنى المتتالية الحسابية في ويكيبيديا في حالة عدم معرفتك بها. يعطي التعقيد O-complexity لخوارزمية ما حدًا أعلى لتعقيد الخوارزمية الفعلي - أي الوقت الأكبر الذي قد تستغرقه الخوارزمية-، بينما تعطي الصيغة Θ تعقيد الخوارزمية الفعلي، حيث نقول أحيانًا أن الصيغة Θ تعطينا حدًا تامًا، وإذا علمت أننا وجدنا حد تعقيدٍ غير تام، فيمكنك استخدام الحرف الصغير o للإشارة إلى ذلك، فمثلًا، إذا كان للخوارزمية التعقيد Θ( n )، فسيكون تعقيدها التام n، وبالتالي سيكون لهذه الخوارزمية O( n ) و O( n2 ) معًا. بما أن الخوارزمية هي Θ( n )، فسيكون حد O( n ) هو الحد التام؛ أما حد O( n2 ) فليس تامًا، ولذلك يمكننا كتابة أن الخوارزمية هي o( n2 ) والتي تُنطق "o الصغير بالنسبة إلى مربع n"، وذلك لتوضيح أن الحد ليس تامًا. كما يُفضَّل إيجاد حدود تامة للخوارزميات لأنها تعطينا مزيدًا من المعلومات حول سلوكها، ولكنه ليس أمرًا سهلًا دائمًا. تمرين 5 حدّد أيًا من الحدود التالية هي حدودًا تامةً وأيها لا، ثم تحقق من صحتها أو خطئها، ويجب عليك استخدام الصيغة o لتحديد الحدود غير التامة: خوارزمية Θ (n) التي لها الحد الأعلى O (n). خوارزمية Θ (n2) التي لها الحد الأعلى O (n3). خوارزمية Θ(1) التي لها الحد الأعلى O (n). خوارزمية Θ (n) التي لها الحد الأعلى O (1). خوارزمية Θ (n) التي لها الحد الأعلى O (2n). الحل الحد تام لأنّ تعقيد Θ وتعقيد O متماثلان في هذه الحالة. الحد غير تام لأنّ تعقيد O أكبر من تعقيد Θ، وقد يكون حد O( n2 ) تامًا، لذلك يمكننا كتابة أن الخوارزمية هي o( n3). الحد غير تام، لأنّ تعقيد O أكبر من تعقيد Θ، وقد يكون حد O( 1 ) تامًا، لذلك يمكننا الإشارة بأنّ الحد O( n ) ليس تامًا من خلال كتابته بالشكل o( n ). الحد خاطئ، فقد اُرتكِب خطأ في حسابه، فلا يمكن أن يكون لخوارزمية Θ( n ) حد أعلى من O( 1 )‎، وذلك لأنّ التعقيد n أكبر من التعقيد 1 -تذكر أنّ O تعطي حدًا أعلى. الحد تام، فقد يبدو مثل حد غير تام، لكن هذا ليس صحيحًا في الواقع، -تذكر أنّ سلوك 2n وn المقارب هو نفسه، وأنّ الصيغتَين O وΘ تهتمان بالسلوك المقارب؛ إذًا لدينا O( 2n ) = O( n )، وبالتالي، فهذا الحد تام لأن التعقيد هو نفس Θ. قد تجد نفسك تائهًا قليلًا في هذه الصيغة الجديدة، ولكن سنقدم صيغتين آخرين بسيطتين بالنسبة للصيغ Θ، وO، وo قبل انتقالنا إلى بعض الأمثلة، ويُستحسَن أن تعرف هاتين الصيغتَين الآن، حيث لن نستخدمهما كثيرًا في هذا المقال لاحقًا. عدّلنا برنامجنا في المثال أعلاه ليصبح أسوأ -أي أخذ المزيد من التعليمات، وبالتالي المزيد من الوقت- وأنشأنا الصيغة O، حيث تُعَدّ الصيغة O ذا مغزىً لأنها تخبرنا بأن برنامجنا لن يكون أبدًا أبطأ من حدٍ معين، ولهذا فهي توفر معلومات قيّمةً تمكننا من القول بأن برنامجنا جيد بما فيه الكفاية، وإذا فعلنا العكس وعدّلنا برنامجنا ليصبح أفضل، ثم أوجدنا تعقيد البرنامج الناتج، فنستخدم الصيغة Ω التي تعطينا تعقيدًا يخبرنا بأن برنامجنا لن يكون أفضل، وهذا مفيد إذا أردنا إثبات أن البرنامج يعمل ببطء أو أن الخوارزمية سيئة، وقد يكون هذا مفيدًا للقول بأن الخوارزمية بطيئة جدًا عند استخدامها في حالة معينة، فمثلًا، خوارزمية Ω( n3 ) ليست أفضل من n3. قد تكون الصيغة Θ( n3 ) سيئًة مثل Θ (n4) أو أسوأ منها، لكننا نعلم أنها سيئة إلى حد ما على الأقل. إذًا تعطينا الصيغة Ω حدًا أدنى لتعقيد خوارزمية، كما يمكننا كتابة الصيغة ω على غرار الصيغة ο عندما يكون الحد ليس تامًا، فمثلًا، خوارزمية Θ ( n3 ) هي ο( n4 ) وω( n2 ) وتُقرَأ Ω( n ) "أوميغا كبيرة بالنسبة إلى n"، بينما تُقرَأ ω( n ) "أوميغا صغيرة بالنسبة إلى n". تمرين 6 اكتب حد O تام وآخر غير تام، وحد Ω تام وآخر غير تام من اختيارك للتعقيدات التالية، ولكن بشرط وجودهما طبعًا: Θ( 1 ) Θ(√n) Θ( n ) Θ( n2 ) Θ( n3 ) الحل هذا هو تطبيق مباشر للتعاريف أعلاه: الحدود التامة هي O( 1 ) وΩ( 1 )، كما يكون حد O غير التام هو O( n ) -تذكّر أن O تعطينا حدًا أعلى-، وبما أن n أكبر من 1، فسيمثِّل حدًا غير تام يمكننا كتابته بالشكل o( n ) أيضًا، كما لا يمكننا إيجاد حد غير تام للصيغة Ω لعدم تمكننا من الحصول على أقل من 1 لهذه الدوال، إذًا يجب تعاملنا مع الحد التام فقط. يجب أن تكون للحدود التامة تعقيد Θ نفسه، لذا فهي O(√n) وΩ(√n) على التوالي؛ أما الحدود غير التامة فقد تكون O( n )، حيث تُعَدّ n أكبر من ‎√n وبالتالي فهي حد أعلى لها. وبما أننا نعلم أن هذا حدًا أعلى غير تام، فيمكننا أيضًا كتابته بالصورة o( n )؛ أما الحد الأدنى غير التام، فيمكننا ببساطة استخدام Ω( 1 )، وبما أننا نعلم أن هذا الحد ليس تامًا، فيمكننا كتابته بالصورة ω( 1. 3 ). الحدود التامة هي O( n ) وΩ( n ). قد يكون الحدان الغير تامين هما ω( 1 ) وo( n3 ) وهي في الواقع حدودٌ سيئة للغاية، لأنها بعيدة كل البعد عن التعقيدات الأصلية، إلا أنها لا تزال صالحة باستخدام التعاريف. الحدود التامة هي O( n2 ) وΩ( n2 ) ويمكننا استخدام ω( 1 ) وo( n3 ) بالنسبة للحدود غير التامة كما في المثال السابق. الحدود التامة هي O( n3 ) وΩ( n3 ) على التوالي، وقد يكون الحدان غير التامَين هما ω(‎n2 √n)‎ وω(n3 √n)، وعلى الرغم من أنّ هذه الحدود ليست تامة، إلا أنها أفضل من تلك الموجودة في جواب رقم 3 و4 من هذا التمرين أعلاه. قد تعطي الصيغتان O وΩ أيضًا حدودًا تامة، وسبب استخدامنا لهما بدلًا من الصيغة Θ هو أننا قد لا نكون قادرين على معرفة ما إذا كان الحد الذي أوجدناه تامًا أم لا، أو ربما لا نرغب في متابعة العملية باستخدام الصيغة Θ التي تحتاج تدقيقًا عميقًا. إذا لم تتذكر تمامًا جميع الرموز المختلفة واستخداماتها، فلا تقلق بشأنها كثيرًا الآن، حيث يمكنك دائمًا العودة والبحث عنها، وأهم الرموز هي O وΘ. لاحظ أيضًا أنه على الرغم من كون الصيغة Ω تعطينا سلوكًا ذو حدٍ منخفض للدالة -أي تحسّن برنامجنا وأصبح ينفّذ تعليماتٍ أقل-، إلا أننا ما زلنا نشير إليها بتحليل "الحالة الأسوأ"، لأننا نزوّد برنامجنا بأسوأ دخلٍ ممكن من n ونحلّل سلوكه في ظل هذا الافتراض. يوضح الجدول التالي الرموز التي قدمناها للتو وتوافقاتها مع الرموز الرياضية المعتادة للمقارنات التي نستخدمها مع الأعداد، كما يعود السبب في عدم استخدامنا للرموز المعتادة هنا واستخدام الأحرف الإغريقية بدلًا منها، إلى الإشارة إلى إجراء مقارنة سلوك مقارب وليس مقارنة بسيطة: 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; } عامل المقارنة المقارب Asymptotic comparison operator عامل المقارنة العددي Numeric comparison operator الخوارزمية هي ( شيء ما )o يوجد عدد < هذا الشيء الخوارزمية هي ( شيء ما )O يوجد عدد ≤ هذا الشيء الخوارزمية هي ( شيء ما )Θ يوجد عدد = هذا الشيء الخوارزمية هي ( شيء ما )Ω يوجد عدد ≥ هذا الشيء الخوارزمية هي ( شيء ما )ω يوجد عدد > هذا الشيء اللوغاريتمات Logarithms هل تعرف ما هي اللوغاريتمات؟ إن كانت إجابتك نعم، فلا تتردد في تخطي هذا القسم، فهذا القسم هو مقدمة لمن ليس على دراية باللوغاريتمات، أو لمن لم يستخدمها كثيرًا مؤخرًا، فهو موجَّهٌ للطلاب الأصغر سنًا، والذين لم يروا اللوغاريتمات في المدرسة بعد. تُعَدّ اللوغاريتمات مهمة بسبب ظهورها بكثرة عند تحليل التعقيد، ويُعَدّ اللوغاريتم عمليةً تُطبَّق على رقم ما ليصبح أصغر، حيث تشبه هذه العملية الجذر التربيعي لرقم إلى حد كبير؛ لذلك إذا كان هناك شيء واحد تريد تذكره حول اللوغاريتمات، فهو أنها تأخذ رقمًا وتجعله أصغر بكثير من الأصل. يوضِّح الشكل الآتي مقارنةً بين الدوال n، و‎√n، وlog( n )، إذ تنمو الدالة n -أو كما تُسمَّى الدالة الخطية linear function- المرسومة باللون الأخضر في أعلى الشكل، أسرع بكثير من دالة الجذر التربيعي المرسومة باللون الأحمر في المنتصف، والتي بدورها تنمو أسرع بكثير من الدالة log( n ) المرسومة باللون الأزرق في الجزء السفلي من هذا الرسم البياني، ويكون الفرق واضحًا تمامًا حتى بالنسبة إلى n صغيرة مثل n = 100. تُعَدّ اللوغاريتمات عمليةً عكسيةً لرفع شيءٍ ما إلى أس مثل الجذور التربيعية التي هي عملية عكسية لتربيع شيءٍ ما، وسنشرح ذلك بمثال. ضع في بالك المعادلة التالية: 2x = 1024 نريد حل هذه المعادلة لإيجاد قيمة x، لذلك لنسأل أنفسنا: ما هو الرقم الذي يجب رفع الأساس 2 إليه حتى نحصل على 1024؟ هذا الرقم هو 10. بالفعل لدينا ‎210 = 1024، وهو أمر سهل التحقق منه؛ كما تساعدنا اللوغاريتمات من خلال الإشارة إلى هذه المشكلة باستخدام صيغة جديدة، فالرقم 10 في هذه الحالة هو لوغاريتم 1024 ونكتبه بالصورة ( log( 1024 ونقرأه "لوغاريتم 1024". بما أننا نستخدم العدد 2 أساسًا، فتسمى هذه اللوغاريتمات لوغاريتمات الأساس 2، كما توجد لوغاريتمات لها أساسات أخرى، ولكننا سنستخدم فقط لوغاريتمات الأساس 2 في هذا المقال، وإذا كنت طالبًا منافسًا في مسابقات دولية ولا تعرف شيئًا عن اللوغاريتمات، فنوصيك بشِدة بالتدرّب على اللوغاريتمات بعد الانتهاء من هذا المقال. تُعَدّ لوغاريتمات الأساس 2 أكثر أنواع اللوغاريتمات شيوعًا في علوم الحاسوب لأنه غالبًا ما يكون لدينا كيانان مختلفان فقط هما: 0 و1، كما نميل أيضًا إلى تقسيم مشكلة كبيرة واحدة إلى نصفين، لذلك ما عليك سوى معرفة لوغاريتمات الأساس 2 لمتابعة هذا المقال. تمرين 7 حُلّ المعادلات أدناه، وأوجد اللوغاريتم في كل حالة باستخدام اللوغاريتمات ذات الأساس 2 فقط: 2x = 64 ‎(22)x= 64 4x = 4 2x = 1 2x + 2x = 32 ‎(2x) * (2x) = 64 الحل لا يتضمن الحل أكثر من تطبيق الأفكار المُعرَّفة أعلاه: يمكننا باستخدام طريقة التجربة والخطأ إيجاد أن x = 6، وبالتالي، log( 64 ) = 6. يمكن كتابة ‎(22)x بالصورة 22x من خلال تطبيق خصائص الأس، إذًا لدينا 2x = 6 لأن log( 64 ) = 6 من النتيجة السابقة، وبالتالي، x = 3. يمكننا كتابة 4 بالشكل 22 باستخدام معرفتنا من المعادلة السابقة، وبهذا تصبح المعادلة ‎(22)x= 4 وهي 22x = 4 نفسها، ونلاحظ أن log( 4 ) = 2 لأن ‎22 = 4، وبالتالي، لدينا أن 2x = 2، وعليه فـ x = 1؛ كما يمكن ملاحظة ذلك بسهولة من المعادلة الأصلية، حيث أن ناتج الرفع للأس 1 هو الأساس نفسه. تذكر أن ناتج الرفع للأس 0 هو 1، لذلك لدينا log( 1 ) = 0، بما أنّ ‎20= 1، وبالتالي، x = 0. لا يمكننا أخذ اللوغاريتم مباشرةً بسبب وجود المجموع، ولكن يمكن ملاحظة أنّ 2x+ 2x هي ‎2 * (2x) نفسها، حيث ضربنا هنا بالعدد 2 أي لهما الأساس نفسه، وبالتالي، ينتج 2x + 1، والآن كل ما علينا فعله هو حل المعادلة 2x + 1= 32، حيث نجد أنّ log( 32 ) = 5، وهكذا x + 1 = 5، وبالتالي، x = 4. نضرب هنا قوتين للعدد 2 معًا، ولذلك يمكننا ضمهما من خلال ملاحظة أن (2x) * (2x) هي 22x نفسها، وبالتالي كل ما علينا فعله هو حل المعادلة 22x= 64 التي حللناها بالفعل أعلاه، حيث x = 3. التعقيد العودي 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 / 2i عنصر في التكرار i بسبب تقسيم المصفوفة في كل تكرار إلى نصفين، مما يعني أننا نقسم عدد عناصرها على 2، أي نضرب المقام بـ 2؛ وإذا فعلنا ذلك i مرة، فسنحصل على n / 2i، إذ يستمر هذا الإجراء ونحصل على عدد أصغر من العناصر مع كل قيمة أكبر للمتغير i، حتى نصل إلى التكرار الأخير الذي يتبقى فيه عنصر واحد فقط، وإذا رغبنا في معرفة التكرار i الذي يتبقى فيه عنصرٌ واحد فقط، فعلينا حل المعادلة التالية: 1 = n / 2i سيكون هذا صحيحًا فقط عندما نصل إلى الاستدعاء النهائي للدالة ()binarySearch، وليس في الحالة العامة، لذلك فإيجاد قيمة i هنا سيساعدنا في العثور على التكرار الذي ستنتهي فيه العودية. وإذا ضربنا كلا الطرفين بـ 2i فسنحصل على: 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( n2 ) وما إلى ذلك بديهيًا، كما أصبحت تعرف الرموز 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 ))، وهذا أفضل بكثير من Θ( n2 ) الذي هو تعقيد خوارزمية الفرز الانتقائي -تذكر أنّ log( n ) أصغر بكثير من n، وبالتالي يكون n * log (n) أصغر بكثير من n * n = n2-، وإذا وجدت ذلك معقدًا، فلا تقلق لأن الأمر ليس سهلًا في المرة الأولى. يسمح لنا تحليل التعقيد بمقارنة الخوارزميات لمعرفة أيها أفضل كما رأيت في هذا المثال الأخير، ويمكننا الآن أن نكون على يقينٍ تام من تفوّق خوارزمية الفرز بالدمج على خوارزمية الفرز الانتقائي للمصفوفات الكبيرة، كما سيكون استخلاص هذا الاستنتاج صعبًا إذا لم تملك الخلفية النظرية لتحليل الخوارزمية. تُستخدَم خوارزميات الفرز التي لها وقت تشغيل Θ( 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

ترميز Big-O هو ترميز رياضي في الأساس يُستخدم لموازنة معدّلات تقارب الدوال، وسنستعرض في هذا المقال استخدامات هذا الترميز في تحليل الخوارزميات وتصنيفها كما يلي. إذا كانت ‎n -> f(n)‎ وn -> g(n)‎ دالتين مُعرّفتين على الأعداد الطبيعية، فسنقول أنّ ‎f = O(g)‎ فقط إذا كانت ‎f(n)/g(n)‎ محصورة bounded عندما يؤول n إلى اللا نهاية. أي أن ‎f = O(g)‎ فقط إذا كان هناك ثابت A، بحيث يكون ‎f(n)/g(n) <= A‎ لكل n. وفي الواقع فإن نطاق استخدام ترميز Big-O أوسع قليلاً في الرياضيات، لكن سنضيّقه في النطاق المُستخدَم في تحليل الخوارزميات للتبسيط، أي الدوال المُعرَّفة على الأعداد الطبيعية والتي ليست لها قيم صفرية أو جذور zero values عندما يؤول n إلى اللانهاية. شرح لنأخذ حالة هاتين الدالتين: ‎f(n) = 100n^2 + 10n + 1‎ 7 والدالة ‎g(n) = n^2‎ من الواضح تمامًا أنهما تؤولان إلى اللانهاية عندما يؤول n إلى اللانهاية. لكن قد لا يكفي أحيانًا أن نعرف النهاية limit، فقد نرغب أيضًا في معرفة السرعة التي تقترب بها الدوال من نهايتها، وهنا يأتي دور ترميز Big-O إذ يساعد على تصنيف الدوال بحسَب سرعة تقاربها. فعندئذ نطبّق التعريف للتحقق ممّا إذا كانت ‎f = O(g)‎ حيث لدينا: ‎f(n)/g(n) = 100 + 10/n + 1/n^2‎ وبما أن ‎10/n‎ يساوي القيمة 10 عندما يكون n=1 ويتناقص مع تزايد قيمة n، وبما أنّ ‎1/n^2‎ تساوي 1 عندما يساوي n القيمة 1 وهو أيضًا يتناقص مع تزايد قيمة n، فنحصل على المتراجحة f(n)/g(n) <= 100 +10 + 1 = 111 وقد تحقّق شرط التعريف هنا لأنّنا وجدنا حدًّا bound للتعبير ‎f(n)/g(n)‎‎ - وهو 111-، ونكون بهذا قد أثبتنا أنّ‎f = O(g)‎‎، ونقول أنّ f هي Big-O لـ ‎n^2‎. هذا يعني أنّ f تؤول إلى اللانهاية بنفس سرعة g تقريبًا. قد يبدو هذا غريبًا في البداية لأنّنا وجدنا أنّ f أكبر بـ 111 مرة من g، أو بعبارة أخرى، عندما تنمو g بمقدار 1، فإن f تنمو بمقدار 111 على أقصى حد. والحقيقة أنّ ترميز Big-O ليس دقيقًا في تصنيف سرعات تقارب الدوال، لهذا نَستخدم علاقة التكافؤ equivalence relationship في الرياضيات عندما نريد تقديرًا دقيقًا للسرعة. لكن إن أردت تصنيف الخوارزميات إلى أصناف عامّة بحسب السرعات، فإنّ Big-O كافية، إذ لن نحتاج إلى التمييز بين دالتين تنمو إحداهما أسرع من الأخرى بعدد محدد من المرات، بل المهم هو التمييز بين الدوال التي تنمو لانهائيًا أسرع من بعضها البعض. على سبيل المثال، في حالة ‎h(n) = n^2*log(n)‎ نلاحظ أنّ ‎h(n)/g(n) = log(n)‎ تؤول إلى ما لانهاية عندما يؤول n إلى ما لا نهاية، لذا فإنّ h ليست من الصنف O (n ^ 2)‎‎، لأنّ h تنمو لانهائيًا أسرع من n ^ 2. وفي مجال تحليل تعقيد الخوارزميات، نكتب ‎f =‎ O(g)‎ للدلالة على أنّ: f = O(g)‎‎ و ‎g = O(f)‎ والتي يمكن تأويلها على أنّ g هي أصغر دالة من الصنف Big-O لــ f؛ أما في الرياضيات فنقول أنّ هاتين الدالتين Big-Theta لبعضها البعض. كيفية الاستخدام أول شيء عليك حسابه عند موازنة أداء الخوارزميات هو عدد العمليات التي تجريها الخوارزمية، وهو ما يُسمّى وقت التعقيد time complexity. ونفترض في هذا النموذج أنّ كل عملية أساسية (الجمع والضرب والمقارنة والتعيين وما إلى ذلك) تستغرق مقدارًا ثابتًا من الوقت، ونحسب عدد هذه العمليات. ونعبر في الغالب عن هذا العدد كدالة لحجم الدخل -الذي نصطلح على تسميته n-، ويؤول هذا العدد (الدالة) في الغالب إلى ما لا نهاية عندما يؤول n إلى ما لا نهاية، أما خلاف ذلك، فنقول أنّ الخوارزمية من النوع O (1)‎‎. ونحن نصنّف الخوارزميات إلى أصناف بحسب سرعات الدوال ونمثّلها بالترميز Big-O: فمثلًا إن قلنا أنّ خوارزميةً ما من النوع الآتي: O (n ^ 2)‎‎ فإنّنا نقصد أنّ عدد العمليات التي تنفّذها الخوارزمية -معبَّرًا عنها كدالة لـ n- هو O (n ^ 2)‎‎. وهو ما يعني أنّ سرعة الخوارزمية تقارب سرعة خوارزمية تجري عددًا من العمليات يساوي مرّبع حجم الدخل أو أسرع. لاحظ لفظة أو أسرع، لقد وضعناها لأنّنا استخدمنا Big-O بدلاً عن Big-Theta، ذلك أنّه من الشائع أن ترى الناس تكتب Big-O، رغم أنّهم يعنون Big-Theta. ونحن نأخذ الحالة الأسوأ في حسابنا عادة عند عدّ العمليات، فإن كانت حلقة تكرارية تُنفَّذ n مرّةً على الأكثر وكانت تحتوي على 5 عمليات، فإنّ عدد العمليات المُقدَّر سيكون 5n. كذلك من الممكن مراعاة متوسط تعقيد الحالة. يمكن أن نأخذ مساحة التخزين بالحسبان كذلك، وهو ما يُسمّى تعقيد المساحة space complexity للخوارزمية، ذلك أن الوقت ليس المورد الوحيد المهم، وفي هذه الحالة نحسُب عدد البايتات التي تشغلها الخوارزمية في الذاكرة كدالة لحجم الدخل، ونستخدم Big-O كما في حالة تعقيد الوقت. مثال عن حلقة بسيطة Simple Loop الدالة التالية تبحث عن أكبر عنصر في المصفوفة: int find_max(const int *array, size_t len) { int max = INT_MIN; for (size_t i = 0; i < len; i++) { if (max < array[i]) { max = array[i]; } } return max; } حجم الدخل هو حجم المصفوفة، والذي سمّيناه ‎len‎ في الشيفرة أعلاه. دعنا الآن نَعُد العمليات. int max = INT_MIN; size_t i = 0; تُنفَّذ هاتان العمليتان مرةً واحدة، لذا فلدينا عمليتان هنا. والآن نعدّ عمليات الحلقة: if (max < array[i]) i++; max = array[i] لمّا كانت هناك 3 عمليات في الحلقة، وكانت الحلقة تُنفَّذ n مرة، فسنضيف ‎3n‎ إلى 2 (العمليتان اللتان حسبناهما من قبل)، ليبلغ الإجمالي ‎3n + 2‎. تجري دالتنا إذن عددًا من العمليات مقداره ‎3n + 2‎ عملية للعثور على أكبر عنصر في المصفوفة (تعقيدها يساوي ‎3n + 2‎). وهذا يعرف بتعددية الحدود polynomial، وأسرع عواملها نموّا هو العامل n، لذا يساوي تعقيدها O (n)‎‎. لعلّك لاحظت أنّ طريقة عدّ العمليات ليست دقيقة، فقد قلنا مثلًا أنّ (max < array)‎ هي عملية واحدة، ولكن اعتمادًا على هندسة الحاسوب فقد تنطوي هذه العبارة على تعليمتين مثلاً، الأولى لقراءة الذاكرة والثانية للمقارنة. وقد اعتبرنا كذلك أنّ جميع العمليات متشابهة رغم أنّ العمليات التي تخصّ الذاكرة على سبيل المثال تكون أبطأ من العمليات الأخرى، كما يختلف أداؤها اختلافًا كبيرًا بسبب تأثيرات التخزين المؤقت cache. كذلك تجاهلنا أيضًا تعليمة الإعادة return وحقيقةَ إنشاء إطار frame خاص بالدالة، وما إلى ذلك من الأمور الجانبية. لكنّ هذا لن يؤثّر في النهاية على تحليل التعقيد، ذلك أنّه مهما كانت طريقة عدّ العمليات، فلن يؤثّر إلا على معامل العامل n وكذلك لن يؤثر على الثابت، لذا ستظل النتيجة O (n)‎‎. ويُظهر التعقيد كيف تتطوّر الخوارزمية مع تطوّر حجم الدخل، بيْد أنّها ليست الجانب الوحيد الذي يمثّل الأداء. مثال عن الحلقات المتشعبة Nested Loops تتحقق الدالة التالية ممّا إذا كانت المصفوفة تحتوي أيّ تكرارات، وذلك عبر المرور على كل عنصر على حدة، ثم المرور مجدّدا على المصفوفة للتحقّق ممّا إذا كان هناك عنصر آخر يساويه. _Bool contains_duplicates(const int *array, size_t len) { for (int i = 0; i < len - 1; i++) { for (int j = 0; j < len; j++) { if (i != j && array[i] == array[j]) { return 1; } } } return 0; } تنفّذ الحلقة الداخلية عند كل تكرار عددًا ثابتًا من العمليات (بغضّ النظر عن قيمة ‎n‎)، كما تنفّذ الحلقة الخارجية أيضًا بعض العمليات الثابتة علاوة على تنفيذ الحلقة الداخلية عدد ‎n‎ مرّة. أيضًا، تنفَّذ الحلقةُ الخارجية نفسها ‎n‎ مرّة، وعليه تُنفّذ العمليات داخل الحلقة الداخلية ‎n^2‎ مرّة بينما تُنفّذ عمليات الحلقة الخارجية ‎n‎ مرّة، أمّا عملية التعيين إلى ‎i‎ فتُتفّذ مرّة واحدة. وهكذا يمكن التعبير عن التعقيد بمعادلة مثل ‎an^2 + bn + c‎، ولمّا كان المعامل الأعلى هو ‎n^2‎، فإنّ ترميز O سيساوي ‎O(n^2)‎. لعلك لاحظت أن هناك فرصة لتحسين الخوارزمية أكثر، إذ يمكن مثلًا تجنّب إجراء نفس المقارنات أكثرة من مرّة. يمكننا أن نبدأ من ‎i + 1‎ في الحلقة الداخلية نظرًا لأنّ جميع العناصر التي تسبقه قد تم التحقق منها سلفًا وقورنت مع جميع عناصر المصفوفة، بما في ذلك العنصر الموجود عند الفهرس ‎i + 1‎. هذا يسمح لنا بحذف الاختبار ‎i == j‎. _Bool faster_contains_duplicates(const int *array, size_t len) { for (int i = 0; i < len - 1; i++) { for (int j = i + 1; j < len; j++) { if (array[i] == array[j]) { return 1; } } } return 0; } كما ترى فإنّ هذا الإصدار أفضل لأنّه يُجري عمليات أقل، لكن كيف نترجم هذا في ترميز Big-O؟ حسنًا، في الإصدار الجديد، يُنفّذ مَتن الحلقة الداخلية المرات ‎1 + 2 + ... + n - 1 = n(n-1)/2‎ لا يزال هذا التعبير كثير الحدود من الدرجة الثانية، لذا سيظلّ التعقيد مساويا لـ ‎O(n^2)‎. وقد قلّلنا التعقيد إذ خفّضنا عدد العمليات إلى النصف تقريبًا، بيْد أنّنا ما زلنا في نفس صنف التعقيد من Big-O. ونحتاج إلى تقسيم عدد العمليات على مقدار يؤول إلى اللا نهاية مع ‎n‎ من أجل تقليل التعقيد إلى صنف أدنى. الخوارزميات اللوغاريتمية‎‎‎‎ لنفترض أنّ لدينا مشكلة ذات حجم n، ولنفترض أنّ حجم مشكلتنا الأصلية ينخفض إلى النصف (n / 2) بعد كل خطوة من خطوات الخوارزمية. أي أنّه في كل خطوة جديدة يصير حجم المشكلة نصف ما كانت عليه في الخطوة التي قبلها: 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; } الخطوة المشكلة 1 n/2 2 n/4 3 n/8 4 n/16 تكون المشكلة محلولة حين يتعذر تقليل حجمها أكثر بعد الخروج من شرط التحقق، أي عندما تكون n مساوية للقيمة 1. لنفترض الآن أنّ حجم المشكلة يساوي n، نريد أن نحسب عدد الخطوات اللازمة لحل الخوارزمية، سنرمز لهذا العدد بالحرف k: عند الخطوة k، سيساوي حجم المشكلة 1 (أي أنّ المشكلة ستكون قد حُلَّت). من جهة أخرى، نعلم أنّه عند الخطوة k، ينبغي أن يساوي حجم المشكلة العدد (n/2^k). من 1، 2، إذًا n = 2k. طبّق دالة اللوغاريتم على كلا الجانبين: log n = k * loge_2 → k = loge n / loge 2 باستخدام المعادلة التالية: logx (m) / logx (n) = logn (m)‎ حيث يرمز التعبير logt‎‎ إلى اللوغاريتم ذي الأساس t، وتصبح النتيجة k = log2 (n)‎‎ أو k = log n ببساطة. انظر المثال التوضيحي التالي: for(int i=1; i<=n; i=i*2) { // إجراء بعض العمليات } إن كان n يساوي 256، فكم تتوقّع أن يكون عدد الخطوات التي ستنفّذها الحلقة أو أي خوارزمية أخرى ينخفض حجم مشكلتها إلى النصف بعد كل خطوة؟ سنرمز للعدد الذي نبحث عنه بالرمز k، ونحسبه على النحو الآتي: k = log2 (256)‎‎. k = log2 (2^8)‎‎ ( نعلم أنّ log(a^a) = 1‎ لكل عدد a‎). k = 8. هذا مثال آخر لتوضيح هذا النوع من الخوارزميات. وهي خوارزمية البحث الثنائي Binary Search Algorithm. int bSearch(int arr[],int size,int item){ int low=0; int high=size-1; while(low<=high){ mid=low+(high-low)/2; if(arr[mid]==item) return mid; else if(arr[mid]<item) low=mid+1; else high=mid-1; } return –1;// لا يوجد } مثال على خوارزمية من الصنف O (log n)‎‎ انظر المشكلة التالية: L قائمة مرتّبة تحتوي n عددًا صحيحًا نسبيًا (n كبيرة جدا)، على سبيل المثال ‎[-5, -2, -1, 0، 1، 2، 4]‎‎ (هنا، n تساوي 7). إذا كانت ‎L‎ تحتوي العدد الصحيح 0، فكيف يمكنك العثور على فهرس 0؟ المقاربة البسيطة أول ما يتبادر إلى الذهن هو قراءة كل فهرس إلى حين العثور على 0، وفي أسوأ الحالات سيكون علينا إجراء ‎n‎ عملية، وعليه فإنّ التعقيد سيساوي O (n)‎‎. لا مشكلة في هذا مع القيم الصغيرة لـ ‎n‎، ولكن هل هناك طريقة أفضل؟ مبدأ الحصار Dichotomy انظر الخوارزمية التالية Python3: a = 0 b = n-1 while True: h = (a+b) // (*) if L[h] == 0: return h elif L[h] > 0: b = h elif L[h] < 0: a = h وفي أسوأ الحالات، علينا الانتظار حتى يتساوى ‎a‎ و‎b‎، لكن كم عدد العمليات التي يتطلبها ذلك؟ قطعًا ليس n لأننا نقسم المسافة بين ‎a‎ و‎b‎ على 2 في كل مرة ندخل إلى الحلقة، لذا فالتعقيد يساوي O (log n)‎‎. إذا صادفت خوارزمية يُقسم حجمها على عدد معيّن (2 أو 3 أو أيّ عدد) بعد كل خطوة، فإنّ تعقيدها سيكون لوغاريتميًا. ترجمة -بتصرّف- للفصل الثالث من كتاب Algorithms Notes for Professionals. اقرأ أيضًا المقالة السابقة: تعقيد الخوارزميات مدخل إلى الخوارزميات دليل شامل عن تحليل تعقيد الخوارزمية مدخل إلى الذكاء الاصطناعي وتعلم الآلة