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

ما الخطوات الثلاث لخوارزمية فرّق تسُد؟

1. Aالتقسيم، والحل، والدمج
2. Bالتخمين، والتحقق، والتكرار
3. Cالفرز، والبحث، والإرجاع
4. Dالقراءة، والحساب، والكتابة

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

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

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

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

ماذا تحسب خوارزمية Floyd–Warshall، وبأي سرعة؟

1. Aأقصر المسارات بين كل أزواج الرؤوس في O(V³)
2. Bأقصر المسارات من رأس مصدر واحد إلى سائر الرؤوس في O(V + E)
3. Cترتيبًا طوبولوجيًا في O(V²)
4. Dشجرة امتداد صغرى في O(E log V)

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

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

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

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

أي حد صحيح لـ log(n!)؟

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

يعمل الفرز بالإدراج في O(n) على المدخلات المرتبة. هل يناقض هذا الحد الأدنى Ω(n log n) للفرز بالمقارنة؟

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