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

أي من أزمنة التنفيذ هذه كثير حدود؟

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

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

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

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

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

كيف تبني خوارزمية Prim شجرة امتداد صغرى؟

1. Aتحذف أغلى حافة حتى لا تبقى دورات
2. Bتُنفّذ البحث بالعرض أولًا وتحتفظ بشجرة BFS
3. Cتُنمّي شجرة واحدة من رأس بداية، مضيفةً أرخص حافة خارجة من الشجرة
4. Dترتب كل الحواف حسب الوزن وتضيف كل حافة ما لم تُشكّل دورة في الغابة

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

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

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

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

تستغرق مسألة حقيبة الظهر 0/1 المحلولة بالبرمجة الديناميكية زمنًا O(nW). لماذا يُسمى هذا شبه كثير الحدود (pseudo-polynomial)؟

1. Aلأنها تعمل فقط عندما W = 0
2. Bلأن W عدد، فيكون الزمن أسّيًا بالنسبة إلى عدد البتات المستخدمة لكتابة W
3. Cلأن n صغيرة دائمًا
4. Dلأن الخوارزمية عشوائية ويتفاوت زمن تشغيلها مع كل مدخل

ما التعقيد الزمني لـ: for i = 1 to n: for (j = i; j ≤ n; j = j + i) نفّذ عملًا O(1)؟

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