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

ما التعقيد الزمني للبحث الخطي في مصفوفة غير مرتبة من n عنصر (في أسوأ الحالات)؟

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

ما العودية (Recursion)؟

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

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

1. A4 ثوانٍ
2. B8 ثوانٍ
3. Cثانيتين
4. Dثانية واحدة

في مصفوفة مرتبة تبحث عن عنصرين مجموعهما يساوي هدفًا بتحريك مؤشر من كل طرف نحو الداخل. ما التعقيد الزمني؟

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

ما التعقيد الزمني للفرز السريع (Quicksort) في أسوأ الحالات؟

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

ما التعقيد الزمني المُطفأ (amortised) لإضافة عنصر إلى نهاية مصفوفة ديناميكية تضاعف سعتها عند امتلائها؟

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

الفرز الطوبولوجي ممكن فقط في:

1. Aالرسوم البيانية ذات الأوزان السالبة
2. Bالرسوم البيانية الموجهة غير الدورية
3. Cالرسوم البيانية التامة
4. Dالرسوم البيانية غير الموجهة

يحقق ضرب كاراتسوبا 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