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

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

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

ماذا تعني f(n) = Θ(g(n))؟

1. Aأن f تنمو أبطأ من g تمامًا
2. Bأن f تنمو بمعدل g نفسه، محصورة من الأعلى والأسفل بمضاعفات ثابتة لـ g
3. Cأن f تنمو أسرع من g تمامًا
4. Dأن f أصغر دائمًا من g لكل n، فتحدّها g من الأعلى ولا تحدّها من الأسفل أبدًا

تبدأ حلقة بـ i = 1 وتضاعف i في كل تكرار حتى i > n. كم تكرارًا تُنفِّذ؟

1. Aنحو n²
2. Bنحو log₂ n
3. Cنحو n
4. Dنحو n / 2

كم مساحة مكدّس تستخدم دالة مضروب عودية بسيطة fact(n) = n × fact(n − 1)؟

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

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

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

ما التعقيد الزمني لضرب مصفوفتين n × n بالحلقة الثلاثية القياسية؟

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

لماذا يكون متوسط البحث في جدول التجزئة O(1) بينما أسوأ الحالات O(n)؟

1. Aدوال التجزئة بطيئة
2. Bيجب فرز المفاتيح أولًا
3. Cقد تتصادم مفاتيح كثيرة في الدلو نفسه
4. Dالوصول إلى المصفوفات يستغرق O(n)

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

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