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

ماذا يصف زمن التنفيذ في الحالة المتوسطة؟

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

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

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

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

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

ما التعقيد الزمني لـ: for i = 1 to n: for j = 1 to i: نفّذ عملًا O(1)؟

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

لماذا يُحذف أساس اللوغاريتم عادةً في O الكبير، كما في O(log n)؟

1. Aلأن اللوغاريتمات تُقرَّب دائمًا إلى أعداد صحيحة
2. Bلأن الأساس لا يهم إلا عندما تكون n صغيرة
3. Cكل اللوغاريتمات في علوم الحاسوب أساسها 10، فهو مفهوم ضمنًا
4. Dلأن اللوغاريتمات ذات الأسس المختلفة لا تختلف إلا بمعامل ثابت

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

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

ما التعقيد الزمني لـ: for i = 1 to n: for (j = i; j ≤ n; j = j + i) نفّذ عملًا O(1)؟

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

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

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