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

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

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

ما التعقيد الزمني للبحث الخطي في مصفوفة غير مرتبة من n عنصر (في أسوأ الحالات)؟

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

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

1. AO الكبير (Big O)
2. Bأوميغا الصغير (Little omega)
3. Cأوميغا الكبير (Big Omega)
4. Dثيتا الكبير (Big Theta)

ما التعقيد الزمني لضرب مصفوفتين n × n بالحلقة الثلاثية القياسية؟

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

كم مساحة مكدّس تستخدم دالة مضروب عودية بسيطة fact(n) = n × fact(n − 1)؟

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

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

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

ما الكلفة المستهلَكة لزيادة عدّاد ثنائي بمقدار واحد، علمًا بأن زيادة واحدة قد تقلب بتات كثيرة؟

1. AO(log n) لكل زيادة
2. BO(n) لكل زيادة
3. CO(1) لكل زيادة
4. DO(n log n) لكل زيادة

أي عبارة عن P و NP صحيحة؟

1. Aثبت أن P ≠ NP
2. Bكل مسألة في P تنتمي أيضًا إلى NP
3. CNP تعني «ليست كثيرة الحدود» (not polynomial)
4. Dلا يمكن التحقق من حلول مسائل NP بسرعة