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

تستغرق خوارزمية O(n) ثلاث ثوانٍ عند n = مليون. كم تستغرق تقريبًا عند n = مليونين؟

1. A12 ثانية
2. B6 ثوانٍ
3. C9 ثوانٍ
4. D3 ثوانٍ

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

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

تبدأ حلقة بـ i = 1 وتضاعف i في كل تكرار حتى i > n. كم تكرارًا تُنفِّذ؟

1. Aنحو n / 2
2. Bنحو log₂ n
3. Cنحو n²
4. Dنحو n

أي خوارزمية فرز مستقرة؟

1. Aالفرز السريع (النسخة الموضعية المعتادة)
2. Bالفرز بالدمج
3. Cالفرز بالكومة
4. Dالفرز بالاختيار (النسخة المعتادة)

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

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

الخوارزمية الجشعة (Greedy):

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

لماذا قد تعطي خوارزمية Dijkstra نتائج خاطئة حين تكون بعض أوزان الحواف سالبة؟

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

يعمل الفرز بالإدراج في O(n) على المدخلات المرتبة. هل يناقض هذا الحد الأدنى Ω(n log n) للفرز بالمقارنة؟

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