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

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

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

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

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

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

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

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

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

كم مقارنة تقريبًا يحتاجها البحث الثنائي في أسوأ الحالات على مصفوفة مرتبة من 1,000,000 عنصر؟

1. Aنحو 20
2. Bنحو 100
3. Cنحو 500,000
4. Dنحو 1,000

ما التعقيد الزمني لـ: for i = 1 to n: (j = 1; while j < n: j = j × 2)؟

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

أخذ طرفي كل حافة في تطابق أعظمي (maximal matching) يعطي غطاءً رأسيًا. ما جودة هذا الغطاء؟

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

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

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