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

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

1. A6 ثوانٍ
2. B9 ثوانٍ
3. C12 ثانية
4. D3 ثوانٍ

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

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

ما حالة الأساس في دالة عودية؟

1. Aالاستدعاء الذي يستهلك أكبر قدر من الذاكرة
2. Bحالة يُجاب عنها مباشرة دون استدعاء عودي آخر
3. Cالحالة ذات المدخلات الأكبر، وتُعالَج قبل أي استدعاءات عودية
4. Dالسطر الأول من الدالة

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

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

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

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

لماذا لا تعطي البرمجة الديناميكية تسريعًا حقيقيًا للفرز بالدمج؟

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

تستغرق مسألة حقيبة الظهر 0/1 المحلولة بالبرمجة الديناميكية زمنًا O(nW). لماذا يُسمى هذا شبه كثير الحدود (pseudo-polynomial)؟

1. Aلأن الخوارزمية عشوائية ويتفاوت زمن تشغيلها مع كل مدخل
2. Bلأن W عدد، فيكون الزمن أسّيًا بالنسبة إلى عدد البتات المستخدمة لكتابة W
3. Cلأن n صغيرة دائمًا
4. Dلأنها تعمل فقط عندما W = 0

ما حل علاقة التكرار T(n) = 2T(n/2) + n log n؟

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