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

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

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

ماذا يصف زمن التنفيذ في أسوأ الحالات لخوارزمية؟

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

زمن تنفيذ خوارزمية O(n). ماذا يُسمى هذا النمو؟

1. Aتربيعي
2. Bخطي
3. Cثابت
4. Dلوغاريتمي

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

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

كم مساحة مكدّس تستخدم دالة مضروب عودية بسيطة fact(n) = n × fact(n − 1)؟

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

كم مستوى لعودية الفرز بالدمج لمصفوفة من n عنصر؟

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

أي تعريف للفئة P صحيح؟

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

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

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