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

ما التعقيد المعتاد لخوارزمية فيها حلقتان متداخلتان تُنفَّذ كل منهما n مرة؟

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

ما خوارزمية القوة الغاشمة؟

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

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

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

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

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

التعقيد الزمني لحساب فيبوناتشي العودي الساذج (fib(n) = fib(n−1) + fib(n−2)) هو:

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

ما التعقيد الزمني لضرب مصفوفتين n × n بالحلقة الثلاثية القياسية؟

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

أخذ طرفي كل حافة في تطابق أعظمي (maximal matching) يعطي غطاءً رأسيًا. ما جودة هذا الغطاء؟

1. Aغطاء رأسي أصغر دائمًا
2. Bضعف حجم الغطاء الرأسي الأصغر على الأكثر
3. Clog n ضعف الأصغر على الأكثر
4. Dجودته مجهولة مقارنةً بالأمثل

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

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