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

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

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

ماذا يصف زمن التنفيذ في أسوأ الحالات لخوارزمية؟

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

ما التعقيد الزمني للبحث الخطي في مصفوفة غير مرتبة من n عنصر (في أسوأ الحالات)؟

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

في مصفوفة مرتبة تبحث عن عنصرين مجموعهما يساوي هدفًا بتحريك مؤشر من كل طرف نحو الداخل. ما التعقيد الزمني؟

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

كم مستوى لعودية الفرز بالدمج لمصفوفة من n عنصر؟

1. Aنحو n
2. Bنحو √n
3. Cنحو n / 2
4. Dنحو log₂ n

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

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

تضرب خوارزمية ستراسن المصفوفات باستخدام 7 بدل 8 عمليات ضرب عودية لكتل نصف الحجم. ما زمن تنفيذها؟

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

لماذا لا يعطي البحث الثنائي زمن O(log n) على قائمة مترابطة أحادية؟

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