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

ما زمن تنفيذ الفرز بالعدّ لـ n عددًا صحيحًا في المدى من 0 إلى k؟

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

ماذا يُسمى النمو O(2ⁿ)؟

1. Aلوغاريتمي
2. Bأسّي
3. Cخطي
4. Dكثير حدود

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

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

الحد الأدنى للفرز القائم على المقارنة في أسوأ الحالات هو:

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

التعقيد الزمني لحساب فيبوناتشي العودي الساذج (fib(n) = fib(n−1) + fib(n−2)) هو:

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

لماذا لا تعطي البرمجة الديناميكية تسريعًا حقيقيًا للفرز بالدمج؟

1. Aلأن الفرز بالدمج ليس له بنية عودية
2. Bلأن الفرز بالدمج O(n) أصلًا
3. Cلأن مسائله الفرعية لا تتداخل، فلا شيء يُعاد استخدامه
4. Dلأن البرمجة الديناميكية لا تعمل إلا على مسائل الرسوم البيانية، لا على المصفوفات

تحل خوارزمية البرمجة الديناميكية Held–Karp مسألة البائع المتجول بدقة. ما زمن تنفيذها لـ n مدينة؟

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

كيف تُقارَن n! و2ⁿ عندما تكون n كبيرة؟

1. Aتنموان بالمعدل نفسه
2. Bn! هي O(n²)
3. Cn! تنمو أسرع من 2ⁿ
4. D2ⁿ تنمو أسرع من n!