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

ما التذكير (Memoisation)؟

1. Aتحرير الذاكرة بعد عودة الدالة
2. Bتخزين نتائج استدعاءات الدوال ليُجاب عن الاستدعاءات المكررة من الذاكرة
3. Cتحويل العودية إلى حلقة مكافئة تلقائيًا فلا حاجة إلى مكدّس استدعاءات
4. Dكتابة تعليقات بجانب كل سطر من الشيفرة

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

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

ما الخطوات الثلاث لخوارزمية فرّق تسُد؟

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

أي خوارزمية تجد أقصر المسارات من مصدر واحد في رسم بياني أوزان أضلاعه غير سالبة؟

1. Aخوارزمية بيلمان–فورد مطلوبة في جميع الحالات
2. Bخوارزمية كروسكال (Kruskal)
3. Cخوارزمية ديكسترا (Dijkstra)
4. Dالبحث بالعمق أولًا (DFS)

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

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

هل يصح القول إن خوارزمية O(n²) هي أيضًا O(n³)؟

1. Aنعم، لأن O الكبير حد أعلى وn² لا تنمو أسرع من n³
2. Bلا، لأن n³ أصغر من n² عندما تكون n كبيرة
3. Cنعم، لكن فقط إذا كانت n أصغر من 100
4. Dلا، لأن O الكبير يجب أن يذكر دائمًا معدل النمو الدقيق للدالة

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

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

لماذا يحتاج أي بحث قائم على المقارنة في مصفوفة مرتبة إلى Ω(log n) مقارنة في أسوأ الحالات؟

1. Aلأن كل مقارنة تستغرق زمنًا لوغاريتميًا
2. Bلأن كل عنصر يجب أن يُقارَن مرة واحدة على الأقل
3. Cلأن شجرة قرار لها n نتيجة ممكنة يجب أن يكون عمقها log₂ n على الأقل
4. Dلأن البحث الثنائي هو الخوارزمية الوحيدة الممكنة، وهو يحتاج إلى log₂ n مقارنة