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

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

1. A12 ثانية
2. B9 ثوانٍ
3. C3 ثوانٍ
4. D6 ثوانٍ

ما التذكير (Memoisation)؟

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

ما التعقيد المعتاد لخوارزمية فيها حلقتان متداخلتان تُنفَّذ كل منهما n مرة؟

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

لماذا تنتقل روتينات فرز كثيرة في المكتبات إلى الفرز بالإدراج للمصفوفات الفرعية الصغيرة جدًا؟

1. Aلأن كلفته الإضافية ضئيلة وهو سريع على المدخلات الصغيرة أو شبه المرتبة
2. Bلأن الخوارزميات العودية لا تتعامل مع مصفوفات أقل من 10 عناصر
3. Cلأن الفرز بالإدراج يستهلك ذاكرة أقل من أي خوارزمية فرز أخرى على المدخلات الكبيرة
4. Dلأن الفرز بالإدراج O(n log n) في أسوأ الحالات

تكون البرمجة الديناميكية مفيدة عندما تحتوي المسألة على:

1. Aلا مسائل فرعية على الإطلاق، فيمكن حلها في خطوة واحدة
2. Bحلقة واحدة
3. Cمسائل فرعية متداخلة وبنية فرعية مثلى
4. Dمدخلات عشوائية فقط

ماذا تحسب خوارزمية Floyd–Warshall، وبأي سرعة؟

1. Aترتيبًا طوبولوجيًا في O(V²)
2. Bشجرة امتداد صغرى في O(E log V)
3. Cأقصر المسارات بين كل أزواج الرؤوس في O(V³)
4. Dأقصر المسارات من رأس مصدر واحد إلى سائر الرؤوس في O(V + E)

أي من مسائل الإرضاء هذه معروف أنه قابل للحل في زمن كثير حدود؟

1. ASAT العامة على صيغ في الصيغة العادية العطفية
2. Bإرضاء الدارات
3. C2-SAT، حيث يحتوي كل بند على حرفيّين (literals) على الأكثر
4. D3-SAT، حيث يحتوي كل بند على ثلاثة حرفيّات بالضبط

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

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