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

ما O الكبير للتعبير 3n² + 5n + 2؟

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

ما التعقيد الزمني للبحث الخطي في مصفوفة غير مرتبة من n عنصر (في أسوأ الحالات)؟

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

الوصول إلى عنصر في مصفوفة عبر فهرسه يستغرق:

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

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

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

الخوارزمية الجشعة (Greedy):

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

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

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

أي من مسائل الإرضاء هذه معروف أنه قابل للحل في زمن كثير حدود؟

1. A2-SAT، حيث يحتوي كل بند على حرفيّين (literals) على الأكثر
2. BSAT العامة على صيغ في الصيغة العادية العطفية
3. C3-SAT، حيث يحتوي كل بند على ثلاثة حرفيّات بالضبط
4. Dإرضاء الدارات

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

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