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

ما زمن تنفيذ الفرز بالعدّ لـ n عددًا صحيحًا في المدى من 0 إلى k؟

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

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

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

ما خوارزمية القوة الغاشمة؟

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

ترتب مصفوفة من n عنصر مرة واحدة ثم تجيب عن k استعلام عضوية بالبحث الثنائي. ما الكلفة الكلية؟

1. AO(n + k)
2. BO(k n log n)
3. CO(nk)
4. DO(n log n + k log n)

أي عبارة صحيحة عن دالة عودية ليس لها حالة أساس قابلة للبلوغ؟

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

ما التعقيد الزمني لحساب عدد فيبوناتشي رقم n بجدول تصاعدي (من الأسفل إلى الأعلى)؟

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

تحل خوارزمية البرمجة الديناميكية Held–Karp مسألة البائع المتجول بدقة. ما زمن تنفيذها لـ n مدينة؟

1. AO(n² 2ⁿ)
2. BO(2^n²)
3. CO(n³)
4. DO(n!)

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

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