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

ما التعقيد الزمني للفرز بالإدراج في أفضل الحالات، على مصفوفة مرتبة مسبقًا؟

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

أي فئة تعقيد تنمو بأسرع ما يمكن عندما تكون n كبيرة؟

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

ماذا يصف زمن التنفيذ في الحالة المتوسطة؟

1. Aالزمن لمدخل متوسط الطول
2. Bالزمن على الحاسوب الأكثر شيوعًا
3. Cالزمن المتوقع على توزيع معين للمدخلات ذات الحجم n
4. Dالقيمة الوسطى بين زمن التنفيذ في أفضل الحالات وفي أسوئها

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

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

في مسألة اختيار الأنشطة، أي قاعدة جشعة تعطي دائمًا أكبر عدد من الأنشطة غير المتداخلة؟

1. Aاختر النشاط الذي يبدأ أبكر
2. Bاختر أقصر نشاط أولًا
3. Cاختر النشاط الذي ينتهي أبكر، ثم كرّر مع الأنشطة المتوافقة
4. Dاختر النشاط الأقل تداخلًا أولًا، ثم كرّر مع الأنشطة المتوافقة

الخوارزمية الجشعة (Greedy):

1. Aتعطي الحل الأمثل دائمًا
2. Bتستخدم العودية فقط
3. Cتجرّب كل حل ممكن
4. Dتتخذ الخيار الأفضل محليًا في كل خطوة

تستغرق مسألة حقيبة الظهر 0/1 المحلولة بالبرمجة الديناميكية زمنًا O(nW). لماذا يُسمى هذا شبه كثير الحدود (pseudo-polynomial)؟

1. Aلأن الخوارزمية عشوائية ويتفاوت زمن تشغيلها مع كل مدخل
2. Bلأن n صغيرة دائمًا
3. Cلأنها تعمل فقط عندما W = 0
4. Dلأن W عدد، فيكون الزمن أسّيًا بالنسبة إلى عدد البتات المستخدمة لكتابة W

تحل خوارزمية البرمجة الديناميكية Held–Karp مسألة البائع المتجول بدقة. ما زمن تنفيذها لـ n مدينة؟

1. AO(2^n²)
2. BO(n³)
3. CO(n!)
4. DO(n² 2ⁿ)