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

ماذا يُسمى النمو O(2ⁿ)؟

1. Aلوغاريتمي
2. Bخطي
3. Cكثير حدود
4. Dأسّي

تستغرق خوارزمية O(n²) ثانية واحدة عند n = 1000. كم تستغرق تقريبًا عند n = 2000؟

1. Aثانيتين
2. Bثانية واحدة
3. C8 ثوانٍ
4. D4 ثوانٍ

ما التذكير (Memoisation)؟

1. Aتحرير الذاكرة بعد عودة الدالة
2. Bكتابة تعليقات بجانب كل سطر من الشيفرة
3. Cتحويل العودية إلى حلقة مكافئة تلقائيًا فلا حاجة إلى مكدّس استدعاءات
4. Dتخزين نتائج استدعاءات الدوال ليُجاب عن الاستدعاءات المكررة من الذاكرة

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

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

في مصفوفة مرتبة تبحث عن عنصرين مجموعهما يساوي هدفًا بتحريك مؤشر من كل طرف نحو الداخل. ما التعقيد الزمني؟

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

كم مستوى لعودية الفرز بالدمج لمصفوفة من n عنصر؟

1. Aنحو n
2. Bنحو log₂ n
3. Cنحو n / 2
4. Dنحو √n

أي تعريف للفئة NP صحيح؟

1. Aالمسائل التي لا تستطيع أي خوارزمية حلها
2. Bالمسائل التي لا يمكن حلها في زمن كثير حدود
3. Cمسائل القرار التي يمكن التحقق من إجاباتها بـ "نعم" في زمن كثير حدود عند إعطاء شهادة
4. Dالمسائل غير كثيرة الحدود

باستخدام المبرهنة الرئيسية (master theorem)، حل T(n) = 8T(n/2) + O(n²) هو:

1. AΘ(n² log n)
2. BΘ(n²)
3. CΘ(n log n)
4. DΘ(n³)