تعقيد الخوارزميات – ⁦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⁩. وتضع شاشة ثانية، «البائع المتجول»، مدنًا على خريطة وتقارن بين القوة الغاشمة، التي تفحص كل الجولات وعددها ⁦(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¹²⁩ خطوة في الثانية

أسئلة للاستكشاف

  1. عندما تتضاعف ⁦n⁩ من ⁦50⁩ إلى ⁦100⁩، كم مرة يكبر ⁦n²⁩، وكم مرة تقريبًا يكبر ⁦n·log₂n⁩؟
  2. لماذا يبقى منحنى ⁦log₂n⁩ شبه مستوٍ بينما يرتفع منحنى ⁦n²⁩ بحدة؟
  3. عند ⁦n = 10⁩، كم مقارنة إضافية يجريها الفرز الفقاعي مقارنة بالفرز السريع، وهل لهذا الفرق أهمية عمليًا؟