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

ماذا يصف زمن التنفيذ في الحالة المتوسطة؟

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

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

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

كيف يعمل الفرز بالاختيار (Selection sort)؟

1. Aيبدّل مرارًا مواضع العناصر المتجاورة الموجودة في ترتيب خاطئ
2. Bيجد مرارًا أصغر عنصر في الجزء غير المرتب ويبدّله إلى المقدمة
3. Cيُدرج كل عنصر في جزء مرتب متنامٍ بالإزاحة
4. Dيقسم المصفوفة إلى نصفين ثم يدمجهما

التعقيد الزمني لحساب فيبوناتشي العودي الساذج (fib(n) = fib(n−1) + fib(n−2)) هو:

1. Aأسّي
2. Bخطي
3. Cلوغاريتمي
4. Dثابت

تُنفِّذ دالة حلقة من n تكرارًا، ثم بشكل منفصل حلقة أخرى من n تكرارًا. ما تعقيدها الزمني؟

1. AO(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 log n)
3. CO(n³)
4. DO(n²)

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

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

أي تعريف للفئة NP صحيح؟

1. Aالمسائل التي لا تستطيع أي خوارزمية حلها
2. Bالمسائل غير كثيرة الحدود
3. Cمسائل القرار التي يمكن التحقق من إجاباتها بـ "نعم" في زمن كثير حدود عند إعطاء شهادة
4. Dالمسائل التي لا يمكن حلها في زمن كثير حدود