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

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

1. A9 ثوانٍ
2. B12 ثانية
3. C3 ثوانٍ
4. D6 ثوانٍ

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

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

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

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

ماذا تحسب خوارزمية Floyd–Warshall، وبأي سرعة؟

1. Aأقصر المسارات بين كل أزواج الرؤوس في O(V³)
2. Bشجرة امتداد صغرى في O(E log V)
3. Cأقصر المسارات من رأس مصدر واحد إلى سائر الرؤوس في O(V + E)
4. Dترتيبًا طوبولوجيًا في O(V²)

ما التعقيد الزمني لحساب عدد فيبوناتشي رقم n بجدول تصاعدي (من الأسفل إلى الأعلى)؟

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

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

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

أي عبارة عن ترميز o الصغير صحيحة؟

1. An = o(n²)، لكن n ليست o(n)
2. Bn = o(n)، لأن كل دالة هي o صغير لنفسها
3. C2n = o(n)، لأن 2n تنمو ببطء
4. Dn² = o(n)

ما التعقيد الزمني لبناء كومة ثنائية من n عنصر غير مرتب بالطريقة التصاعدية (bottom-up)؟

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