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

ماذا يصف زمن التنفيذ في أسوأ الحالات لخوارزمية؟

1. Aالزمن الذي تستغرقه على أصغر مدخل
2. Bالزمن المتوقع الذي تستغرقه على مدخل عشوائي بحجم n
3. Cأقصى زمن تستغرقه على كل المدخلات ذات الحجم n
4. Dالزمن الذي تستغرقه على حاسوب بطيء

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

1. AO (O الكبير)
2. BΩ (أوميغا الكبير)
3. Co (o الصغير)
4. DΘ (ثيتا الكبير)

زمن تنفيذ خوارزمية O(n). ماذا يُسمى هذا النمو؟

1. Aثابت
2. Bلوغاريتمي
3. Cخطي
4. Dتربيعي

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

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

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

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

كم مقارنة تقريبًا يحتاجها البحث الثنائي في أسوأ الحالات على مصفوفة مرتبة من 1,000,000 عنصر؟

1. Aنحو 100
2. Bنحو 1,000
3. Cنحو 20
4. Dنحو 500,000

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

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

الفرز الطوبولوجي ممكن فقط في:

1. Aالرسوم البيانية التامة
2. Bالرسوم البيانية الموجهة غير الدورية
3. Cالرسوم البيانية غير الموجهة
4. Dالرسوم البيانية ذات الأوزان السالبة