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

أي مما يلي ينمو بأبطأ ما يمكن عندما تصبح n كبيرة؟

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

أي خوارزمية فرز تبدّل مرارًا مواضع العناصر المتجاورة الموجودة في ترتيب خاطئ؟

1. Aالفرز بالكومة (Heap sort)
2. Bالفرز السريع (Quicksort)
3. Cالفرز بالدمج (Merge sort)
4. Dالفرز الفقاعي (Bubble sort)

أي خوارزمية فرز تختار محورًا وتقسم المصفوفة إلى عناصر أصغر وعناصر أكبر؟

1. Aالفرز بالدمج
2. Bالفرز بالإدراج
3. Cالفرز السريع (Quicksort)
4. Dالفرز الفقاعي

ما حل علاقة التكرار T(n) = T(n − 1) + O(n)؟

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

في مصفوفة مرتبة تبحث عن عنصرين مجموعهما يساوي هدفًا بتحريك مؤشر من كل طرف نحو الداخل. ما التعقيد الزمني؟

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

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

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

ما حل علاقة التكرار T(n) = 2T(n/2) + n log n؟

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

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

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