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

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

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

ما التعقيد الزمني للفرز بالإدراج في أفضل الحالات، على مصفوفة مرتبة مسبقًا؟

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

أي من أزمنة التنفيذ هذه كثير حدود؟

1. AO(n³)
2. BO(nⁿ)
3. CO(n!)
4. DO(2ⁿ)

بقطع نقدية من فئات 1 و3 و4 ومبلغ 6، كم قطعة تستخدم الطريقة الجشعة "أكبر قطعة أولًا" مقارنةً بالحل الأمثل؟

1. Aتستخدم الجشعة 3 قطع، والأمثل 3
2. Bتستخدم الجشعة 3 قطع، والأمثل 2
3. Cتستخدم الجشعة قطعتين، والأمثل 2
4. Dتستخدم الجشعة 4 قطع، والأمثل 3

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

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

ماذا يعني أن لمسألة بنية فرعية مثلى؟

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

أي تقنية تعطي زمن تشغيل متوقعًا O(n log n) للفرز السريع على أي مدخلات؟

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

ماذا سيترتب لو وجد أحدهم خوارزمية كثيرة حدود لمسألة NP-تامة واحدة؟

1. Aتنتقل تلك المسألة وحدها إلى P
2. Bيمكن حل كل مسألة في NP في زمن كثير حدود، أي P = NP
3. Cتصبح كل الخوارزميات ذات الزمن الأسّي خطية فورًا
4. Dتصبح مسألة التوقف قابلة للحسم