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

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

1. AO الكبير (Big O)
2. Bثيتا الكبير (Big Theta)
3. Cأوميغا الصغير (Little omega)
4. Dأوميغا الكبير (Big Omega)

أي مما يلي ينمو بأبطأ ما يمكن عندما تصبح n كبيرة؟

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

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

1. A9 ثوانٍ
2. B3 ثوانٍ
3. C6 ثوانٍ
4. D12 ثانية

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

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

في مصفوفة مرتبة تبحث عن عنصرين مجموعهما يساوي هدفًا بتحريك مؤشر من كل طرف نحو الداخل. ما التعقيد الزمني؟

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

بقطع نقدية من فئات 1 و3 و4 ومبلغ 6، كم قطعة تستخدم الطريقة الجشعة "أكبر قطعة أولًا" مقارنةً بالحل الأمثل؟

1. Aتستخدم الجشعة 3 قطع، والأمثل 2
2. Bتستخدم الجشعة 4 قطع، والأمثل 3
3. Cتستخدم الجشعة 3 قطع، والأمثل 3
4. Dتستخدم الجشعة قطعتين، والأمثل 2

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

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

لماذا لا يعطي البحث الثنائي زمن O(log n) على قائمة مترابطة أحادية؟

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