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

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

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

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

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

يقيس التعقيد المكاني:

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

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

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

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

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

لماذا يُحذف أساس اللوغاريتم عادةً في O الكبير، كما في O(log n)؟

1. Aلأن الأساس لا يهم إلا عندما تكون n صغيرة
2. Bلأن اللوغاريتمات ذات الأسس المختلفة لا تختلف إلا بمعامل ثابت
3. Cكل اللوغاريتمات في علوم الحاسوب أساسها 10، فهو مفهوم ضمنًا
4. Dلأن اللوغاريتمات تُقرَّب دائمًا إلى أعداد صحيحة

أي من مسائل الإرضاء هذه معروف أنه قابل للحل في زمن كثير حدود؟

1. A3-SAT، حيث يحتوي كل بند على ثلاثة حرفيّات بالضبط
2. B2-SAT، حيث يحتوي كل بند على حرفيّين (literals) على الأكثر
3. Cإرضاء الدارات
4. DSAT العامة على صيغ في الصيغة العادية العطفية

أي تعريف للفئة NP صحيح؟

1. Aالمسائل التي لا تستطيع أي خوارزمية حلها
2. Bمسائل القرار التي يمكن التحقق من إجاباتها بـ "نعم" في زمن كثير حدود عند إعطاء شهادة
3. Cالمسائل غير كثيرة الحدود
4. Dالمسائل التي لا يمكن حلها في زمن كثير حدود