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

ما التعقيد المعتاد لخوارزمية فيها حلقتان متداخلتان تُنفَّذ كل منهما n مرة؟

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

يقيس التعقيد المكاني:

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

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

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

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

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

كيف تبني خوارزمية Prim شجرة امتداد صغرى؟

1. Aتحذف أغلى حافة حتى لا تبقى دورات
2. Bتُنمّي شجرة واحدة من رأس بداية، مضيفةً أرخص حافة خارجة من الشجرة
3. Cتُنفّذ البحث بالعرض أولًا وتحتفظ بشجرة BFS
4. Dترتب كل الحواف حسب الوزن وتضيف كل حافة ما لم تُشكّل دورة في الغابة

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

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

ما الكلفة الزمنية والمكانية لحساب عدد فيبوناتشي رقم n بحلقة لا تحتفظ إلا بآخر قيمتين؟

1. Aزمن O(n) ومساحة O(1)
2. Bزمن O(2ⁿ) ومساحة O(1)
3. Cزمن O(log n) ومساحة O(n)
4. Dزمن O(n) ومساحة O(n)

يحقق ضرب كاراتسوبا T(n) = 3T(n/2) + O(n). ما حل هذه العلاقة؟

1. AΘ(n²)
2. BΘ(n^{log₂ 3})، أي نحو n^1,585
3. CΘ(n log n)
4. DΘ(n³)