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

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

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

ماذا يصف زمن التنفيذ في أسوأ الحالات لخوارزمية؟

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

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

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

لماذا تنتقل روتينات فرز كثيرة في المكتبات إلى الفرز بالإدراج للمصفوفات الفرعية الصغيرة جدًا؟

1. Aلأن الخوارزميات العودية لا تتعامل مع مصفوفات أقل من 10 عناصر
2. Bلأن كلفته الإضافية ضئيلة وهو سريع على المدخلات الصغيرة أو شبه المرتبة
3. Cلأن الفرز بالإدراج O(n log n) في أسوأ الحالات
4. Dلأن الفرز بالإدراج يستهلك ذاكرة أقل من أي خوارزمية فرز أخرى على المدخلات الكبيرة

ماذا تحسب خوارزمية Floyd–Warshall، وبأي سرعة؟

1. Aترتيبًا طوبولوجيًا في O(V²)
2. Bأقصر المسارات بين كل أزواج الرؤوس في O(V³)
3. Cشجرة امتداد صغرى في O(E log V)
4. Dأقصر المسارات من رأس مصدر واحد إلى سائر الرؤوس في O(V + E)

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

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

يحقق ضرب كاراتسوبا T(n) = 3T(n/2) + O(n). ما حل هذه العلاقة؟

1. AΘ(n²)
2. BΘ(n³)
3. CΘ(n^{log₂ 3})، أي نحو n^1,585
4. DΘ(n log n)

ما الكلفة المستهلَكة لزيادة عدّاد ثنائي بمقدار واحد، علمًا بأن زيادة واحدة قد تقلب بتات كثيرة؟

1. AO(n) لكل زيادة
2. BO(1) لكل زيادة
3. CO(n log n) لكل زيادة
4. DO(log n) لكل زيادة