ورقة عمل الخوارزميات والتعقيد مع الإجابات

أي ترميز يصف حدًا أدنى للنمو؟

1. AΩ (أوميغا الكبير)
2. BO (O الكبير)
3. CΘ (ثيتا الكبير)
4. Do (o الصغير)

زمن تنفيذ خوارزمية O(n). ماذا يُسمى هذا النمو؟

1. Aثابت
2. Bلوغاريتمي
3. Cتربيعي
4. Dخطي

كم ذاكرة إضافية يستخدمها الفرز بالدمج القياسي المعتمد على المصفوفات؟

1. AO(1)
2. BO(log n)
3. CO(n²)
4. DO(n)

تُنفِّذ دالة حلقة من n تكرارًا، ثم بشكل منفصل حلقة أخرى من n تكرارًا. ما تعقيدها الزمني؟

1. AO(2ⁿ)
2. BO(log n)
3. CO(n²)
4. DO(n)

ما التعقيد الزمني لحساب عدد فيبوناتشي رقم n بجدول تصاعدي (من الأسفل إلى الأعلى)؟

1. AO(n)
2. BO(log n)
3. CO(n²)
4. DO(2ⁿ)

لماذا تنتقل روتينات فرز كثيرة في المكتبات إلى الفرز بالإدراج للمصفوفات الفرعية الصغيرة جدًا؟

1. Aلأن الخوارزميات العودية لا تتعامل مع مصفوفات أقل من 10 عناصر
2. Bلأن كلفته الإضافية ضئيلة وهو سريع على المدخلات الصغيرة أو شبه المرتبة
3. Cلأن الفرز بالإدراج يستهلك ذاكرة أقل من أي خوارزمية فرز أخرى على المدخلات الكبيرة
4. Dلأن الفرز بالإدراج O(n log n) في أسوأ الحالات

كيف تكشف خوارزمية Bellman–Ford دورة سالبة الوزن قابلة للبلوغ من المصدر؟

1. Aتعدّ الدورات بالبحث بالعمق أولًا
2. Bبعد V − 1 جولة تتحقق مما إذا كان يمكن بعدُ إرخاء أي حافة
3. Cتتحقق مما إذا كانت لأي حافة وزن سالب
4. Dتُنفّذ خوارزمية Dijkstra مرتين وتقارن نتيجتَي المسافات

أي أمرين يجب إثباتهما لإثبات أن مسألة القرار X هي NP-تامة؟

1. Aأن X تنتمي إلى NP، وأن مسألة NP-تامة معروفة تُختزل إلى X في زمن كثير حدود
2. Bأن X تُختزل إلى مسألة في P، وأن X تنتمي إلى NP
3. Cأن X ليس لها خوارزمية كثيرة حدود، وأن X قابلة للحسم
4. Dأن X تنتمي إلى P، وأن X تُختزل إلى SAT