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

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

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

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

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

ما التعقيد الزمني للبحث الثنائي في مصفوفة مرتبة؟

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

كم مستوى لعودية الفرز بالدمج لمصفوفة من n عنصر؟

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

يستخدم فرز سريع العنصر الأول محورًا دائمًا. على أي مدخل يُظهر سلوك أسوأ الحالات؟

1. Aمصفوفة مرتبة مسبقًا
2. Bمصفوفة طولها 2
3. Cمصفوفة بترتيب عشوائي
4. Dمصفوفة عناصرها كلها مختلفة

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

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

باستخدام المبرهنة الرئيسية (master theorem)، حل T(n) = 8T(n/2) + O(n²) هو:

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

تُظهر مسألة التوقف أنه:

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