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

أي ترميز يصف حدًا أدنى للنمو؟

1. AΩ (أوميغا الكبير)
2. BO (O الكبير)
3. Co (o الصغير)
4. DΘ (ثيتا الكبير)

ماذا يصف زمن التنفيذ في الحالة المتوسطة؟

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

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

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

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

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

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

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

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

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

ما الكلفة المستهلَكة لزيادة عدّاد ثنائي بمقدار واحد، علمًا بأن زيادة واحدة قد تقلب بتات كثيرة؟

1. AO(log n) لكل زيادة
2. BO(1) لكل زيادة
3. CO(n) لكل زيادة
4. DO(n log n) لكل زيادة

الفرز الطوبولوجي ممكن فقط في:

1. Aالرسوم البيانية التامة
2. Bالرسوم البيانية ذات الأوزان السالبة
3. Cالرسوم البيانية غير الموجهة
4. Dالرسوم البيانية الموجهة غير الدورية