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

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

1. Aثانية واحدة
2. Bثانيتين
3. C4 ثوانٍ
4. D8 ثوانٍ

ماذا يتطلب البحث الثنائي في مدخلاته؟

1. Aألا تتجاوز المصفوفة 1000 عنصر
2. Bأن تكون المصفوفة مرتبة
3. Cأن يكون طول المصفوفة قوة للعدد اثنين
4. Dألا تحتوي المصفوفة إلا أعدادًا موجبة

ما التعقيد الزمني للبحث الثنائي في مصفوفة مرتبة؟

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

ما زمن تنفيذ الفرز الجذري LSD على n عددًا صحيحًا من d خانة في الأساس k؟

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

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

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

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

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

أي عبارة عن ترميز o الصغير صحيحة؟

1. A2n = o(n)، لأن 2n تنمو ببطء
2. Bn² = o(n)
3. Cn = o(n)، لأن كل دالة هي o صغير لنفسها
4. Dn = o(n²)، لكن n ليست o(n)

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

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