أسئلة تدريبية مجانية متعددة الخيارات في الخوارزميات والتعقيد مع تلميحات وشروح، بثلاثة مستويات: المصطلحات والحقائق الأساسية, تطبيق المفاهيم, الحالات والتحليل.
أي فئة تعقيد تنمو بأسرع ما يمكن عندما تكون n كبيرة؟
عمل جيد. هل تريد التالية؟هل أنت مستعد للمسألة التالية؟ 5 مسائل جديدة كل يوم، في كل موضوع.
الخوارزمية قائمة منتهية من الخطوات الدقيقة تحل مسألة ما، مثل فرز قائمة أو إيجاد اسم في دليل الهاتف.
يمكن لخوارزميتين حل المسألة نفسها لكنهما تستغرقان زمنين مختلفين جدًا. ويصف التعقيد كيف ينمو العمل عندما يكبر المدخل.
يسمى حجم المدخل n: عدد العناصر المراد فرزها، أو طول قائمة، أو عدد العقد في بيان.
تخيّل البحث عن اسم في دليل هاتف من 1000 صفحة. قراءة كل صفحة تحتاج إلى 1000 خطوة على الأكثر. وفتحه في المنتصف وتنصيف المجال كل مرة يحتاج إلى نحو 10 خطوات.
تعقيد الزمن يعدّ الخطوات. وتعقيد المساحة يعدّ الذاكرة الإضافية. وكلاهما يُكتب دالةً في n.
عادةً تنظر إلى أسوأ حالة: أكبر عمل على كل المدخلات ذات الحجم n. وأحيانًا يُطلب الحالة المتوسطة أو أفضل حالة.
الإجابة: 4 ثوانٍ. مضاعفة n تضرب n² في 2² = 4، فينتقل الزمن من نحو 1 إلى نحو 4 ثوانٍ. وثانيتان هي الجواب للنمو الخطي، و8 لـ n³.
يحتفظ رمز O الكبيرة بما يهم للقيم الكبيرة لـ n فقط. تُسقط العوامل الثابتة وتُبقي الحد الأسرع نموًا فقط.
عندما n = 1000 يكون الحد n² يساوي 3 000 000 بينما 5n يساوي 5000 فقط. فالحدود الأصغر بالكاد تغيّر المجموع.
تتكرر هذه الفئات دائمًا، من الأبطأ نموًا إلى الأسرع:
O الكبيرة حدّ أعلى: ينمو العمل بهذه السرعة على الأكثر. وΩ (أوميغا الكبيرة) حدّ أدنى، وΘ (ثيتا) حدّ محكم، أعلى وأدنى معًا.
أساس اللوغاريتم لا يهم في O الكبيرة، لأن اللوغاريتمات بأسس مختلفة تختلف بعامل ثابت فقط.
الإجابة: O(n²). عند القيم الكبيرة لـ n يهيمن الحد n²، ويُسقط العامل الثابت 2. أما O(n) فتُبقي الحد الخطأ، وO(2n²) تنسى إسقاط الثابت.
تظهر بضع خوارزميات في كل مقرر تقريبًا. احفظ تعقيداتها كحقائق.
الدالة التعاودية تستدعي نفسها على مدخل أصغر حتى تبلغ الحالة الأساسية التي تجيب عنها مباشرةً. ويُكتب زمن تشغيلها على شكل علاقة تعاودية:
ثلاث أفكار تصميمية تستحق المعرفة. فرّق تسد يقسم ويحل ويدمج. والجشع يأخذ الخيار الأفضل محليًا في كل خطوة. والبرمجة الديناميكية تخزّن إجابات المسائل الفرعية المتداخلة لكي تُحسب مرة واحدة.
الإجابة: O(n²). مع محاور سيئة يترك كل تقسيم n − 1 عنصرًا في جهة واحدة، فيعطي O(n²). أما O(n log n) فهي حالته المتوسطة، وهي أسوأ حالة للفرز بالدمج.
لإيجاد تعقيد الزمن لقطعة من الشيفرة:
في سؤال نظري، سمِّ أولًا الخوارزمية أو الفكرة التي يصفها، ثم استحضر تعقيدها وشروطها (مدخل مرتّب، أوزان غير سالبة، مسائل فرعية متداخلة).
تابع كل خطوة. حاول أن تتوقّع الخطوة التالية قبل أن تفتحها.
ما تعقيد الزمن لهذه الشيفرة؟ for i = 1 to n: (j = 1; while j < n: j = j × 2)
n هو العدد الذي تعمل الحلقات حتى بلوغه.
يتغير i من 1 إلى n بخطوة 1، فتُنفَّذ الحلقة الخارجية n مرة.
يأخذ j القيم 1 و2 و4 و8 و… ويتوقف عند بلوغ n. بعد k جولة j = 2k، فتتوقف الحلقة بعد نحو log₂ n جولة.
الحلقة الداخلية داخل الخارجية، لذا تُضرب الأعداد.
عندما n = 1024 تُنفَّذ الحلقة الداخلية log₂ 1024 = 10 مرات، فيُنفَّذ الجسم 1024 · 10 = 10 240 مرة. وهذا أقل بكثير من n² = 1 048 576.
O(n log n)
الإجابة: O(n). الحلقات المتتالية تُجمع: n + n = 2n، ويُسقط الثابت، فتكون O(n). وO(n²) تصح فقط إذا كانت إحدى الحلقتين داخل الأخرى.
تضم P المسائل التي يمكن حلها في زمن حدودي. وتضم NP المسائل التي يمكن التحقق من حلولها في زمن حدودي. كل مسألة في P هي في NP؛ أما هل P = NP فلا يزال مجهولًا.
أي ترميز يصف حدًا أعلى للنمو؟
يعطي O حدًا أعلى، ويعطي Ω حدًا أدنى، ويعطي Θ حدًا محكمًا.
في مصفوفة مرتبة تبحث عن عنصرين مجموعهما يساوي هدفًا بتحريك مؤشر من كل طرف نحو الداخل. ما التعقيد الزمني؟
إذا كان المجموع صغيرًا جدًا يتحرك المؤشر الأيسر يمينًا، وإذا كان كبيرًا جدًا يتحرك المؤشر الأيمن يسارًا، فيكون هناك n خطوة على الأكثر.
تضرب خوارزمية ستراسن المصفوفات باستخدام 7 بدل 8 عمليات ضرب عودية لكتل نصف الحجم. ما زمن تنفيذها؟
مع a = 7 وb = 2 تهيمن nlog₂ 7 على عمل الجمع O(n²)، فيكون الزمن نحو n2,81.
يمكن لخوارزميتين حل المسألة نفسها لكنهما تستغرقان زمنين مختلفين جدًا. ويصف التعقيد كيف ينمو العمل عندما يكبر المدخل.
يسمى حجم المدخل n: عدد العناصر المراد فرزها، أو طول قائمة، أو عدد العقد في بيان.
لكل سؤال أربعة خيارات، واحد منها فقط صحيح. هل علِقت؟ افتح تلميحًا صغيرًا أولًا، والشرح الكامل فقط عندما تحتاج إليه.