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

ما زمن تنفيذ الفرز بالعدّ لـ n عددًا صحيحًا في المدى من 0 إلى k؟

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

أي استراتيجية تصميم يستخدمها الفرز بالدمج؟

1. Aالاختيار الجشع
2. Bالبرمجة الديناميكية
3. Cالقوة الغاشمة
4. Dفرّق تسُد

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

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

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

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

ما التعقيد الزمني لضرب مصفوفتين n × n بالحلقة الثلاثية القياسية؟

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

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

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

تحل خوارزمية البرمجة الديناميكية Held–Karp مسألة البائع المتجول بدقة. ما زمن تنفيذها لـ n مدينة؟

1. AO(2^n²)
2. BO(n!)
3. CO(n² 2ⁿ)
4. DO(n³)

يمكن إيجاد أقصر المسارات البسيطة في زمن كثير حدود. ما المعروف عن إيجاد أطول مسار بسيط بين رأسين في رسم بياني عام؟

1. Aأنه غير قابل للحسم
2. Bأنه قابل للحل دائمًا في O(V + E)
3. Cأنه NP-صعب
4. Dأنه يمكن حله بخوارزمية Dijkstra مع أوزان معكوسة الإشارة