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

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

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

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

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

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

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

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

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

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

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

ما التعقيد الزمني لـ: for i = 1 to n: (j = 1; while j < n: j = j × 2)؟

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

الفرز الطوبولوجي ممكن فقط في:

1. Aالرسوم البيانية غير الموجهة
2. Bالرسوم البيانية ذات الأوزان السالبة
3. Cالرسوم البيانية الموجهة غير الدورية
4. Dالرسوم البيانية التامة

تضرب خوارزمية ستراسن المصفوفات باستخدام 7 بدل 8 عمليات ضرب عودية لكتل نصف الحجم. ما زمن تنفيذها؟

1. AΘ(n^{log₂ 7})، أي نحو n^2,81
2. BΘ(n²)
3. CΘ(n³)
4. DΘ(n² log n)