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

ما التعقيد الزمني للفرز بالإدراج في أسوأ الحالات؟

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

أي فئة تعقيد تنمو بأسرع ما يمكن عندما تكون n كبيرة؟

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

ما التعقيد المعتاد لخوارزمية فيها حلقتان متداخلتان تُنفَّذ كل منهما n مرة؟

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

تكون البرمجة الديناميكية مفيدة عندما تحتوي المسألة على:

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

ما التعقيد الزمني لـ: for i = 1 to n: for j = 1 to i: نفّذ عملًا O(1)؟

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

ما حل علاقة التكرار T(n) = 2T(n − 1) + O(1)؟

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

أي عبارة عن ترميز o الصغير صحيحة؟

1. An² = o(n)
2. Bn = o(n²)، لكن n ليست o(n)
3. Cn = o(n)، لأن كل دالة هي o صغير لنفسها
4. D2n = o(n)، لأن 2n تنمو ببطء

لإثبات أن مسألة جديدة X هي NP-صعبة، ماذا يجب أن تفعل؟

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