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

أي استراتيجية تصميم يستخدمها الفرز بالدمج؟

1. Aفرّق تسُد
2. Bالاختيار الجشع
3. Cالبرمجة الديناميكية
4. Dالقوة الغاشمة

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

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

ما التعقيد الزمني للبحث الثنائي في مصفوفة مرتبة؟

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

لماذا تنتقل روتينات فرز كثيرة في المكتبات إلى الفرز بالإدراج للمصفوفات الفرعية الصغيرة جدًا؟

1. Aلأن الفرز بالإدراج يستهلك ذاكرة أقل من أي خوارزمية فرز أخرى على المدخلات الكبيرة
2. Bلأن كلفته الإضافية ضئيلة وهو سريع على المدخلات الصغيرة أو شبه المرتبة
3. Cلأن الفرز بالإدراج O(n log n) في أسوأ الحالات
4. Dلأن الخوارزميات العودية لا تتعامل مع مصفوفات أقل من 10 عناصر

هل يصح القول إن خوارزمية O(n²) هي أيضًا O(n³)؟

1. Aلا، لأن n³ أصغر من n² عندما تكون n كبيرة
2. Bنعم، لأن O الكبير حد أعلى وn² لا تنمو أسرع من n³
3. Cلا، لأن O الكبير يجب أن يذكر دائمًا معدل النمو الدقيق للدالة
4. Dنعم، لكن فقط إذا كانت n أصغر من 100

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

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

ما الكلفة المستهلَكة لزيادة عدّاد ثنائي بمقدار واحد، علمًا بأن زيادة واحدة قد تقلب بتات كثيرة؟

1. AO(log n) لكل زيادة
2. BO(n) لكل زيادة
3. CO(n log n) لكل زيادة
4. DO(1) لكل زيادة

ماذا سيترتب لو وجد أحدهم خوارزمية كثيرة حدود لمسألة NP-تامة واحدة؟

1. Aيمكن حل كل مسألة في NP في زمن كثير حدود، أي P = NP
2. Bتصبح مسألة التوقف قابلة للحسم
3. Cتنتقل تلك المسألة وحدها إلى P
4. Dتصبح كل الخوارزميات ذات الزمن الأسّي خطية فورًا