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

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

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

ما O الكبير للتعبير 3n² + 5n + 2؟

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

ماذا يعني أن عملية تُنفَّذ في زمن O(1)؟

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

يستخدم فرز سريع العنصر الأول محورًا دائمًا. على أي مدخل يُظهر سلوك أسوأ الحالات؟

1. Aمصفوفة طولها 2
2. Bمصفوفة بترتيب عشوائي
3. Cمصفوفة عناصرها كلها مختلفة
4. Dمصفوفة مرتبة مسبقًا

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

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

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

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

كيف تُقارَن n! و2ⁿ عندما تكون n كبيرة؟

1. An! تنمو أسرع من 2ⁿ
2. B2ⁿ تنمو أسرع من n!
3. Cn! هي O(n²)
4. Dتنموان بالمعدل نفسه

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

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