تعقيد الخوارزميات – O(log n)، O(n)، O(n log n)، O(n²) وسباق فرز
علوم الحاسوبالخوارزميات وحل المشكلات15–16 سنة
كيف تستخدم هذه المحاكاة غالبًا؟
استخدمها مع صفّك: يفتحها الطلاب من رابط أو رمز QR دون الحاجة إلى حساب.
يرسم مخطط عدد الخطوات مقابل حجم المدخلات n للدوال log₂n و n و n·log₂n و n²، ومعه أعداد المقارنات المقيسة مباشرة للفرز الفقاعي والفرز السريع. يسحب الطالب مؤشر n على المخطط ليقرأ القيم، ثم يضغط «سباق» ليشاهد الخوارزميتين تفرزان المصفوفة نفسها بمعدل الخطوات نفسه: ينتهي الفرز السريع (n log n) قبل الفرز الفقاعي (n²)، ويتسع الفارق كلما زادت n. وتضع شاشة ثانية، «البائع المتجول»، مدنًا على خريطة وتقارن بين القوة الغاشمة، التي تفحص كل الجولات وعددها (n − 1)!/2 فتحتاج سريعًا إلى زمن غير معقول، وبين خوارزمية أقرب جار الاستدلالية السريعة.
الدرس: تقييم الخوارزميات: عدد العمليات مقابل حجم المدخلات، ترميز O الكبير، المقارنة بين الفرز الفقاعي والفرز السريع
ماذا تعرض
يصف تعقيد الخوارزمية كيف يزداد عدد العمليات مع زيادة حجم المدخلات n، مع إهمال العوامل الثابتة. يقارن المخطط log₂n و n و n·log₂n و n²، وتُظهر الأعداد المقيسة أن الفرز الفقاعي يجري نحو n²/2 مقارنة والفرز السريع نحو 1.4·n·log₂n. وبعض المسائل أسوأ بكثير: تجرّب شاشة البائع المتجول كل جولة ممكنة، وعددها (n − 1)!/2، فكل مدينة إضافية تضاعف العمل أضعافًا كثيرة، و16 مدينة تستغرق ساعات. أما خوارزمية استدلالية مثل أقرب جار فتجيب في n(n − 1)/2 خطوة، بسرعة ولكن ليس دائمًا بأقصر جولة.
طريقة الاستخدام
اسحب على المخطط لتغيير n، وشغّل «مقياس لوغاريتمي لمحور الخطوات» إذا تباعدت المنحنيات، ثم اضغط «سباق» لتشاهد الفرز. بعد ذلك اضغط «البائع»: انقر على الخريطة لإضافة مدن، واضغط «القوة الغاشمة» و«أقرب جار»، وقارن بين الجولتين وعدد الخطوات. غيّر «عدد المدن» و«سرعة الحاسوب» لترى كيف ينفجر الزمن.
المعاملات القابلة للتغيير
- حجم البيانات n 4–100
- المنحنيات النظرية المعروضة log₂n، n، n·log₂n، n², n و n², log₂n و n و n·log₂n, n و n² و 2ⁿ و n!
- مقياس لوغاريتمي لمحور الخطوات
- سرعة السباق 5–200 خطوة/s
- الشاشة مخطط التعقيد, البائع المتجول
- عدد المدن (البائع المتجول) 4–16
- البذرة العشوائية للمدن 1–999
- سرعة الحاسوب 10⁶ خطوة في الثانية, 10⁹ خطوة في الثانية, 10¹² خطوة في الثانية
أسئلة للاستكشاف
- عندما تتضاعف n من 50 إلى 100، كم مرة يكبر n²، وكم مرة تقريبًا يكبر n·log₂n؟
- لماذا يبقى منحنى log₂n شبه مستوٍ بينما يرتفع منحنى n² بحدة؟
- عند n = 10، كم مقارنة إضافية يجريها الفرز الفقاعي مقارنة بالفرز السريع، وهل لهذا الفرق أهمية عمليًا؟