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

زمن تنفيذ خوارزمية O(n). ماذا يُسمى هذا النمو؟

1. Aتربيعي
2. Bخطي
3. Cثابت
4. Dلوغاريتمي

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

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

الوصول إلى عنصر في مصفوفة عبر فهرسه يستغرق:

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

ماذا يقيس التحليل المستهلَك (amortised)؟

1. Aالكلفة المتوقعة على مدخلات عشوائية
2. Bكلفة الخوارزمية على أفضل مدخل
3. Cكلفة أغلى عملية منفردة في أي موضع من السلسلة
4. Dمتوسط الكلفة لكل عملية على أسوأ سلسلة من العمليات

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

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

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

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

ما الكلفة الزمنية والمكانية لحساب عدد فيبوناتشي رقم n بحلقة لا تحتفظ إلا بآخر قيمتين؟

1. Aزمن O(n) ومساحة O(1)
2. Bزمن O(2ⁿ) ومساحة O(1)
3. Cزمن O(log n) ومساحة O(n)
4. Dزمن O(n) ومساحة O(n)

تستغرق مسألة حقيبة الظهر 0/1 المحلولة بالبرمجة الديناميكية زمنًا O(nW). لماذا يُسمى هذا شبه كثير الحدود (pseudo-polynomial)؟

1. Aلأن W عدد، فيكون الزمن أسّيًا بالنسبة إلى عدد البتات المستخدمة لكتابة W
2. Bلأن الخوارزمية عشوائية ويتفاوت زمن تشغيلها مع كل مدخل
3. Cلأن n صغيرة دائمًا
4. Dلأنها تعمل فقط عندما W = 0