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

تبدأ حلقة بـ i = 1 وتضاعف i في كل تكرار حتى i > n. كم تكرارًا تُنفِّذ؟

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

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

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

ما الخوارزمية؟

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

في مسألة اختيار الأنشطة، أي قاعدة جشعة تعطي دائمًا أكبر عدد من الأنشطة غير المتداخلة؟

1. Aاختر النشاط الذي ينتهي أبكر، ثم كرّر مع الأنشطة المتوافقة
2. Bاختر النشاط الأقل تداخلًا أولًا، ثم كرّر مع الأنشطة المتوافقة
3. Cاختر النشاط الذي يبدأ أبكر
4. Dاختر أقصر نشاط أولًا

هل يصح القول إن خوارزمية O(n²) هي أيضًا O(n³)؟

1. Aلا، لأن O الكبير يجب أن يذكر دائمًا معدل النمو الدقيق للدالة
2. Bلا، لأن n³ أصغر من n² عندما تكون n كبيرة
3. Cنعم، لأن O الكبير حد أعلى وn² لا تنمو أسرع من n³
4. Dنعم، لكن فقط إذا كانت n أصغر من 100

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

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

أي أمرين يجب إثباتهما لإثبات أن مسألة القرار X هي NP-تامة؟

1. Aأن X تنتمي إلى P، وأن X تُختزل إلى SAT
2. Bأن X تُختزل إلى مسألة في P، وأن X تنتمي إلى NP
3. Cأن X ليس لها خوارزمية كثيرة حدود، وأن X قابلة للحسم
4. Dأن X تنتمي إلى NP، وأن مسألة NP-تامة معروفة تُختزل إلى X في زمن كثير حدود

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

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