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

ما التعقيد الزمني للبحث بالعمق أولًا (DFS) على رسم بياني مخزّن بقوائم التجاور؟

1. AO(E log V)
2. BO(V + E)
3. CO(V × E)
4. DO(V²)

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

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

ماذا تعني f(n) = Θ(g(n))؟

1. Aأن f أصغر دائمًا من g لكل n، فتحدّها g من الأعلى ولا تحدّها من الأسفل أبدًا
2. Bأن f تنمو أبطأ من g تمامًا
3. Cأن f تنمو بمعدل g نفسه، محصورة من الأعلى والأسفل بمضاعفات ثابتة لـ g
4. Dأن f تنمو أسرع من g تمامًا

ماذا تحسب خوارزمية Floyd–Warshall، وبأي سرعة؟

1. Aشجرة امتداد صغرى في O(E log V)
2. Bأقصر المسارات من رأس مصدر واحد إلى سائر الرؤوس في O(V + E)
3. Cترتيبًا طوبولوجيًا في O(V²)
4. Dأقصر المسارات بين كل أزواج الرؤوس في O(V³)

ماذا يقيس التحليل المستهلَك (amortised)؟

1. Aالكلفة المتوقعة على مدخلات عشوائية
2. Bكلفة أغلى عملية منفردة في أي موضع من السلسلة
3. Cمتوسط الكلفة لكل عملية على أسوأ سلسلة من العمليات
4. Dكلفة الخوارزمية على أفضل مدخل

لماذا لا تعطي البرمجة الديناميكية تسريعًا حقيقيًا للفرز بالدمج؟

1. Aلأن الفرز بالدمج O(n) أصلًا
2. Bلأن الفرز بالدمج ليس له بنية عودية
3. Cلأن البرمجة الديناميكية لا تعمل إلا على مسائل الرسوم البيانية، لا على المصفوفات
4. Dلأن مسائله الفرعية لا تتداخل، فلا شيء يُعاد استخدامه

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

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

أي عبارة عن ترميز o الصغير صحيحة؟

1. An = o(n)، لأن كل دالة هي o صغير لنفسها
2. Bn = o(n²)، لكن n ليست o(n)
3. Cn² = o(n)
4. D2n = o(n)، لأن 2n تنمو ببطء