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

أي مما يلي ينمو بأبطأ ما يمكن عندما تصبح n كبيرة؟

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

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

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

أي ترميز يصف حدًا أدنى للنمو؟

1. AΘ (ثيتا الكبير)
2. BΩ (أوميغا الكبير)
3. CO (O الكبير)
4. Do (o الصغير)

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

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

هل يصح القول إن خوارزمية O(n²) هي أيضًا O(n³)؟

1. Aلا، لأن n³ أصغر من n² عندما تكون n كبيرة
2. Bنعم، لأن O الكبير حد أعلى وn² لا تنمو أسرع من n³
3. Cنعم، لكن فقط إذا كانت n أصغر من 100
4. Dلا، لأن O الكبير يجب أن يذكر دائمًا معدل النمو الدقيق للدالة

لماذا لا تعطي البرمجة الديناميكية تسريعًا حقيقيًا للفرز بالدمج؟

1. Aلأن الفرز بالدمج ليس له بنية عودية
2. Bلأن الفرز بالدمج O(n) أصلًا
3. Cلأن البرمجة الديناميكية لا تعمل إلا على مسائل الرسوم البيانية، لا على المصفوفات
4. Dلأن مسائله الفرعية لا تتداخل، فلا شيء يُعاد استخدامه

ما التعقيد الزمني لبناء كومة ثنائية من n عنصر غير مرتب بالطريقة التصاعدية (bottom-up)؟

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

كيف تكشف خوارزمية Bellman–Ford دورة سالبة الوزن قابلة للبلوغ من المصدر؟

1. Aتعدّ الدورات بالبحث بالعمق أولًا
2. Bتتحقق مما إذا كانت لأي حافة وزن سالب
3. Cتُنفّذ خوارزمية Dijkstra مرتين وتقارن نتيجتَي المسافات
4. Dبعد V − 1 جولة تتحقق مما إذا كان يمكن بعدُ إرخاء أي حافة