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

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

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

ما العودية (Recursion)؟

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

أي فئة تعقيد تنمو بأسرع ما يمكن عندما تكون n كبيرة؟

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

كم مقارنة تقريبًا يحتاجها البحث الثنائي في أسوأ الحالات على مصفوفة مرتبة من 1,000,000 عنصر؟

1. Aنحو 100
2. Bنحو 20
3. Cنحو 1,000
4. Dنحو 500,000

ما زمن تنفيذ الفرز الجذري LSD على n عددًا صحيحًا من d خانة في الأساس k؟

1. AO(d(n + k))
2. BO(n log n)
3. CO(dn log k)
4. DO(n²)

حل العلاقة التكرارية T(n) = 2T(n/2) + O(n) هو:

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

تستغرق مسألة حقيبة الظهر 0/1 المحلولة بالبرمجة الديناميكية زمنًا O(nW). لماذا يُسمى هذا شبه كثير الحدود (pseudo-polynomial)؟

1. Aلأنها تعمل فقط عندما W = 0
2. Bلأن n صغيرة دائمًا
3. Cلأن W عدد، فيكون الزمن أسّيًا بالنسبة إلى عدد البتات المستخدمة لكتابة W
4. Dلأن الخوارزمية عشوائية ويتفاوت زمن تشغيلها مع كل مدخل

ما زمن تنفيذ خوارزمية Dijkstra مع كومة ثنائية على رسم بياني فيه V رأسًا وE حافة؟

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