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

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

1. A3 ثوانٍ
2. B6 ثوانٍ
3. C12 ثانية
4. D9 ثوانٍ

ما التعقيد الزمني للفرز بالدمج في أسوأ الحالات؟

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

ما الخطوات الثلاث لخوارزمية فرّق تسُد؟

1. Aالتخمين، والتحقق، والتكرار
2. Bالتقسيم، والحل، والدمج
3. Cالفرز، والبحث، والإرجاع
4. Dالقراءة، والحساب، والكتابة

أي خوارزمية فرز مستقرة؟

1. Aالفرز بالكومة
2. Bالفرز بالدمج
3. Cالفرز بالاختيار (النسخة المعتادة)
4. Dالفرز السريع (النسخة الموضعية المعتادة)

ما حل علاقة التكرار T(n) = T(n − 1) + O(1)؟

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

ما التعقيد الزمني لخوارزمية البرمجة الديناميكية القياسية لأطول تتابع جزئي مشترك لسلسلتين طولهما m وn؟

1. AO(mn)
2. BO(m + n)
3. CO(2^m+n)
4. DO(mn log n)

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

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

كيف تُصنَّف مسألة البائع المتجول؟

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