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

ما O الكبير للتعبير 3n² + 5n + 2؟

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

كيف يعمل الفرز بالاختيار (Selection sort)؟

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

ما العودية (Recursion)؟

1. Aطريقة فرز
2. Bدالة تستدعي نفسها على مدخلات أصغر
3. Cنوع من بنى البيانات
4. Dحلقة لا تنتهي أبدًا

الحد الأدنى للفرز القائم على المقارنة في أسوأ الحالات هو:

1. AΩ(n log n)
2. BΩ(n²)
3. CΩ(n)
4. DΩ(log n)

في مصفوفة مرتبة تبحث عن عنصرين مجموعهما يساوي هدفًا بتحريك مؤشر من كل طرف نحو الداخل. ما التعقيد الزمني؟

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

كم مقارنة تقريبًا يحتاجها البحث الثنائي في أسوأ الحالات على مصفوفة مرتبة من 1,000,000 عنصر؟

1. Aنحو 20
2. Bنحو 100
3. Cنحو 500,000
4. Dنحو 1,000

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

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

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

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