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

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

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

ما قيمة log₂ 1024؟

1. A12
2. B512
3. C32
4. D10

ما التعقيد الزمني للفرز بالإدراج في أفضل الحالات، على مصفوفة مرتبة مسبقًا؟

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

الحد الأدنى للفرز القائم على المقارنة في أسوأ الحالات هو:

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

حل العلاقة التكرارية T(n) = 2T(n/2) + O(n) هو:

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

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

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

لماذا يحتاج أي بحث قائم على المقارنة في مصفوفة مرتبة إلى Ω(log n) مقارنة في أسوأ الحالات؟

1. Aلأن البحث الثنائي هو الخوارزمية الوحيدة الممكنة، وهو يحتاج إلى log₂ n مقارنة
2. Bلأن شجرة قرار لها n نتيجة ممكنة يجب أن يكون عمقها log₂ n على الأقل
3. Cلأن كل عنصر يجب أن يُقارَن مرة واحدة على الأقل
4. Dلأن كل مقارنة تستغرق زمنًا لوغاريتميًا

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

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