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