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

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

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

ماذا تعني f(n) = Θ(g(n))؟

1. Aأن f أصغر دائمًا من g لكل n، فتحدّها g من الأعلى ولا تحدّها من الأسفل أبدًا
2. Bأن f تنمو أسرع من g تمامًا
3. Cأن f تنمو أبطأ من g تمامًا
4. Dأن f تنمو بمعدل g نفسه، محصورة من الأعلى والأسفل بمضاعفات ثابتة لـ g

أي فئة تعقيد تنمو بأسرع ما يمكن عندما تكون n كبيرة؟

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

يجد البحث بالعرض أولًا في رسم بياني غير موزون:

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

الحد الأدنى للفرز القائم على المقارنة في أسوأ الحالات هو:

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

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

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

تُظهر مسألة التوقف أنه:

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

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

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