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

ما التعقيد الزمني للبحث الثنائي في مصفوفة مرتبة؟

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

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

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

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

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

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

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

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

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

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

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

تضرب خوارزمية ستراسن المصفوفات باستخدام 7 بدل 8 عمليات ضرب عودية لكتل نصف الحجم. ما زمن تنفيذها؟

1. AΘ(n²)
2. BΘ(n^{log₂ 7})، أي نحو n^2,81
3. CΘ(n³)
4. DΘ(n² log n)

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

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