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

تُسمى المسألة عادةً قابلة للمعالجة (tractable) إذا:

1. Aلم يكن بالإمكان حلها إلا بتجربة كل الاحتمالات
2. Bأمكن حلها في زمن ثابت
3. Cأمكن حلها في زمن كثير حدود
4. Dلم يكن لها حل

ما الخوارزمية؟

1. Aأي برنامج حاسوبي له واجهة رسومية
2. Bلغة برمجة مصممة لكتابة الصيغ الرياضية
3. Cبنية بيانات تخزّن الأعداد
4. Dسلسلة منتهية من الخطوات المحددة جيدًا تحل مسألة

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

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

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

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

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

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

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

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

أي حد صحيح لـ log(n!)؟

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

تضرب خوارزمية ستراسن المصفوفات باستخدام 7 بدل 8 عمليات ضرب عودية لكتل نصف الحجم. ما زمن تنفيذها؟

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