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

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

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

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

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

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

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

ما التعقيد الزمني لخوارزمية البرمجة الديناميكية القياسية لأطول تتابع جزئي مشترك لسلسلتين طولهما m وn؟

1. AO(m + n)
2. BO(mn log n)
3. CO(2^m+n)
4. DO(mn)

ما التعقيد الزمني لـ: for i = 1 to n: (j = 1; while j < n: j = j × 2)؟

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

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

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

باستخدام المبرهنة الرئيسية (master theorem)، حل T(n) = 8T(n/2) + O(n²) هو:

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

لماذا قد تعطي خوارزمية Dijkstra نتائج خاطئة حين تكون بعض أوزان الحواف سالبة؟

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