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

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

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

أي خوارزمية فرز تختار محورًا وتقسم المصفوفة إلى عناصر أصغر وعناصر أكبر؟

1. Aالفرز بالدمج
2. Bالفرز بالإدراج
3. Cالفرز السريع (Quicksort)
4. Dالفرز الفقاعي

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

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

ما التعقيد الزمني لـ: 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²)

ما التعقيد الزمني لخوارزمية Bellman–Ford على رسم بياني فيه V رأسًا وE حافة؟

1. AO(V³ × E)
2. BO(V × E)
3. CO(E log V)
4. DO(V + E)

تُنفِّذ دالة حلقة من n تكرارًا، ثم بشكل منفصل حلقة أخرى من n تكرارًا. ما تعقيدها الزمني؟

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

يعمل الفرز بالإدراج في O(n) على المدخلات المرتبة. هل يناقض هذا الحد الأدنى Ω(n log n) للفرز بالمقارنة؟

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

هل 2²ⁿ تنتمي إلى O(2ⁿ)؟

1. Aلا، لأن 2²ⁿ = 4ⁿ و4ⁿ / 2ⁿ = 2ⁿ تنمو بلا حد
2. Bنعم، لأن المعاملات الثابتة في الأس تُهمَل دائمًا في O الكبير
3. Cلا، لأن 2²ⁿ تنمو أبطأ من 2ⁿ
4. Dنعم، لأن كلتيهما أسيتان