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

ما التعقيد المعتاد لخوارزمية فيها حلقتان متداخلتان تُنفَّذ كل منهما n مرة؟

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

ماذا يعني أن عملية تُنفَّذ في زمن O(1)؟

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

ما خوارزمية القوة الغاشمة؟

1. Aخوارزمية تعمل على معالجات كثيرة
2. Bخوارزمية تجرّب كل الحلول المرشحة الممكنة
3. Cخوارزمية تستخدم العودية دائمًا
4. Dخوارزمية تخمّن إجابة عشوائيًا

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

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

ما التعقيد الزمني لخوارزمية البرمجة الديناميكية القياسية لأطول تتابع جزئي مشترك لسلسلتين طولهما m وn؟

1. AO(mn)
2. BO(2^m+n)
3. CO(m + n)
4. DO(mn log n)

ترتب مصفوفة من n عنصر مرة واحدة ثم تجيب عن k استعلام عضوية بالبحث الثنائي. ما الكلفة الكلية؟

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

أي تقنية تعطي زمن تشغيل متوقعًا O(n log n) للفرز السريع على أي مدخلات؟

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

ما حل علاقة التكرار T(n) = 2T(n/2) + n log n؟

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