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

ما التعقيد الزمني للبحث الخطي في مصفوفة غير مرتبة من n عنصر (في أسوأ الحالات)؟

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

ما التعقيد الزمني للبحث بالعمق أولًا (DFS) على رسم بياني مخزّن بقوائم التجاور؟

1. AO(V + E)
2. BO(V²)
3. CO(V × E)
4. DO(E log V)

ما O الكبير للتعبير 3n² + 5n + 2؟

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

كم مساحة مكدّس تستخدم دالة مضروب عودية بسيطة fact(n) = n × fact(n − 1)؟

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

هل يصح القول إن خوارزمية O(n²) هي أيضًا O(n³)؟

1. Aنعم، لأن O الكبير حد أعلى وn² لا تنمو أسرع من n³
2. Bلا، لأن n³ أصغر من n² عندما تكون n كبيرة
3. Cلا، لأن O الكبير يجب أن يذكر دائمًا معدل النمو الدقيق للدالة
4. Dنعم، لكن فقط إذا كانت n أصغر من 100

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

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

يحقق ضرب كاراتسوبا T(n) = 3T(n/2) + O(n). ما حل هذه العلاقة؟

1. AΘ(n²)
2. BΘ(n log n)
3. CΘ(n^{log₂ 3})، أي نحو n^1,585
4. DΘ(n³)

أي عبارة عن P و NP صحيحة؟

1. Aكل مسألة في P تنتمي أيضًا إلى NP
2. BNP تعني «ليست كثيرة الحدود» (not polynomial)
3. Cثبت أن P ≠ NP
4. Dلا يمكن التحقق من حلول مسائل NP بسرعة