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

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

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

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

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

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

1. Aثانيتين
2. B8 ثوانٍ
3. Cثانية واحدة
4. D4 ثوانٍ

حل العلاقة التكرارية T(n) = 2T(n/2) + O(n) هو:

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

ما زمن تنفيذ الفرز الجذري LSD على n عددًا صحيحًا من d خانة في الأساس k؟

1. AO(d(n + k))
2. BO(n log n)
3. CO(n²)
4. DO(dn log k)

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

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

ما الفرق بين مسألة غير قابلة للحسم ومسألة غير قابلة للمعالجة؟

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

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

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