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

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

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

أي مما يلي ينمو بأبطأ ما يمكن عندما تصبح n كبيرة؟

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

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

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

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

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

لماذا يُحذف أساس اللوغاريتم عادةً في O الكبير، كما في O(log n)؟

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

ما التعقيد الزمني لـ: for i = 1 to n: for j = 1 to i: نفّذ عملًا O(1)؟

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

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

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

أي خوارزمية تجد شجرة ممتدة صغرى بإضافة أرخص ضلع لا يُكوّن دورة بشكل متكرر؟

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