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

تُسمى المسألة عادةً قابلة للمعالجة (tractable) إذا:

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

ما التعقيد الزمني للفرز بالدمج في أسوأ الحالات؟

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

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

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

ما التعقيد الزمني المُطفأ (amortised) لإضافة عنصر إلى نهاية مصفوفة ديناميكية تضاعف سعتها عند امتلائها؟

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

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

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

ترتب مصفوفة من n عنصر مرة واحدة ثم تجيب عن k استعلام عضوية بالبحث الثنائي. ما الكلفة الكلية؟

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

كيف تُصنَّف مسألة البائع المتجول؟

1. Aتنتمي إلى P لأن خوارزمية Dijkstra تحلها بزيارة كل مدينة مرة واحدة
2. Bنسخة القرار في P لكن نسخة التحسين NP-تامة
3. Cنسخة القرار NP-تامة ونسخة التحسين NP-صعبة
4. Dغير قابلة للحسم

أي حد صحيح لـ log(n!)؟

1. AΘ(log n)
2. BΘ(n²)
3. CΘ(n)
4. DΘ(n log n)