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

تستغرق خوارزمية O(n²) ثانية واحدة عند n = 1000. كم تستغرق تقريبًا عند n = 2000؟

1. Aثانية واحدة
2. B4 ثوانٍ
3. C8 ثوانٍ
4. Dثانيتين

ما حالة الأساس في دالة عودية؟

1. Aالسطر الأول من الدالة
2. Bالاستدعاء الذي يستهلك أكبر قدر من الذاكرة
3. Cالحالة ذات المدخلات الأكبر، وتُعالَج قبل أي استدعاءات عودية
4. Dحالة يُجاب عنها مباشرة دون استدعاء عودي آخر

ما زمن تنفيذ الفرز بالعدّ لـ n عددًا صحيحًا في المدى من 0 إلى k؟

1. AO(n + k)
2. BO(n²)
3. CO(k log n)
4. DO(n 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الفرز بالكومة

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

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

أي من مسائل الإرضاء هذه معروف أنه قابل للحل في زمن كثير حدود؟

1. ASAT العامة على صيغ في الصيغة العادية العطفية
2. B3-SAT، حيث يحتوي كل بند على ثلاثة حرفيّات بالضبط
3. Cإرضاء الدارات
4. D2-SAT، حيث يحتوي كل بند على حرفيّين (literals) على الأكثر