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

تستغرق خوارزمية O(n²) ثانية واحدة عند n = 1000. كم تستغرق تقريبًا عند n = 2000؟

1. Aثانيتين
2. B8 ثوانٍ
3. C4 ثوانٍ
4. Dثانية واحدة

الوصول إلى عنصر في مصفوفة عبر فهرسه يستغرق:

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

ما التعقيد الزمني للفرز بالدمج في أسوأ الحالات؟

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

ما التعقيد الزمني المُطفأ (amortised) لإضافة عنصر إلى نهاية مصفوفة ديناميكية تضاعف سعتها عند امتلائها؟

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

حل العلاقة التكرارية T(n) = 2T(n/2) + O(n) هو:

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

تُنفِّذ دالة حلقة من n تكرارًا، ثم بشكل منفصل حلقة أخرى من n تكرارًا. ما تعقيدها الزمني؟

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

لماذا يكون متوسط البحث في جدول التجزئة O(1) بينما أسوأ الحالات O(n)؟

1. Aيجب فرز المفاتيح أولًا
2. Bقد تتصادم مفاتيح كثيرة في الدلو نفسه
3. Cالوصول إلى المصفوفات يستغرق O(n)
4. Dدوال التجزئة بطيئة

ما الفرق بين مسألة غير قابلة للحسم ومسألة غير قابلة للمعالجة؟

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