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

زمن تنفيذ خوارزمية O(n). ماذا يُسمى هذا النمو؟

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

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

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

تُسمى المسألة عادةً قابلة للمعالجة (tractable) إذا:

1. Aلم يكن لها حل
2. Bأمكن حلها في زمن ثابت
3. Cلم يكن بالإمكان حلها إلا بتجربة كل الاحتمالات
4. Dأمكن حلها في زمن كثير حدود

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

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

كم مقارنة تقريبًا يحتاجها البحث الثنائي في أسوأ الحالات على مصفوفة مرتبة من 1,000,000 عنصر؟

1. Aنحو 20
2. Bنحو 500,000
3. Cنحو 1,000
4. Dنحو 100

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

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

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

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

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

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