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

ماذا يصف زمن التنفيذ في أسوأ الحالات لخوارزمية؟

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

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

1. Aأوميغا الصغير (Little omega)
2. BO الكبير (Big O)
3. Cثيتا الكبير (Big Theta)
4. Dأوميغا الكبير (Big Omega)

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

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

ما حل علاقة التكرار T(n) = 2T(n − 1) + O(1)؟

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

ما حل علاقة التكرار T(n) = T(n − 1) + O(1)؟

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

تكون البرمجة الديناميكية مفيدة عندما تحتوي المسألة على:

1. Aمسائل فرعية متداخلة وبنية فرعية مثلى
2. Bحلقة واحدة
3. Cلا مسائل فرعية على الإطلاق، فيمكن حلها في خطوة واحدة
4. Dمدخلات عشوائية فقط

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

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

كيف تُقارَن n! و2ⁿ عندما تكون n كبيرة؟

1. An! تنمو أسرع من 2ⁿ
2. Bتنموان بالمعدل نفسه
3. Cn! هي O(n²)
4. D2ⁿ تنمو أسرع من n!