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

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

1. AO (O الكبير)
2. BΩ (أوميغا الكبير)
3. CΘ (ثيتا الكبير)
4. Do (o الصغير)

ما التعقيد الزمني لإيجاد أكبر قيمة في مصفوفة غير مرتبة من n عددًا؟

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

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

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

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

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

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

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

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

تحل خوارزمية البرمجة الديناميكية Held–Karp مسألة البائع المتجول بدقة. ما زمن تنفيذها لـ n مدينة؟

1. AO(n!)
2. BO(n³)
3. CO(n² 2ⁿ)
4. DO(2^n²)

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

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