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

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

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

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

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

ما الخطوات الثلاث لخوارزمية فرّق تسُد؟

1. Aالتقسيم، والحل، والدمج
2. Bالقراءة، والحساب، والكتابة
3. Cالتخمين، والتحقق، والتكرار
4. Dالفرز، والبحث، والإرجاع

التعقيد الزمني لحساب فيبوناتشي العودي الساذج (fib(n) = fib(n−1) + fib(n−2)) هو:

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

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

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

ماذا يعني أن لمسألة بنية فرعية مثلى؟

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

أي عبارة صحيحة عن اختيار العنصر الأصغر رقم k في مصفوفة غير مرتبة؟

1. Aيحتاج الاختيار دائمًا إلى Ω(n log n) لأنه يتطلب الفرز
2. Bيعمل Quickselect في زمن متوقع O(n)، وتضمن طريقة وسيط الوسائط O(n) في أسوأ الحالات
3. Cالاختيار ممكن فقط في O(n²)
4. Dيعمل Quickselect في O(log n) في أسوأ الحالات لأنه يعود على جانب واحد فقط من المحور

ماذا سيترتب لو وجد أحدهم خوارزمية كثيرة حدود لمسألة NP-تامة واحدة؟

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