Notice: Undefined index: options in /home/egyresmagadmin/web/egyresmag.com/public_html/wp-content/plugins/elementor-pro/modules/theme-builder/widgets/site-logo.php on line 192

التدوين المقارب

التدوين-المقارب

|||

ستسمع بهذه المصطلحات مراراً و تكراراً عند الحديث عن الخوارزميات، فالرموز التي سنتحدث عنها اليوم هي ما ستستمح لك بالتعبير عن فعالية خوارزمية ما من الناحية الزمنية (تعقيدها الزمني) و هو أسلوب رياضي يعتمد على ربط تعقيد الخوارزمية بجحم الدخل … فمثلاً عند البحث عن قيمة ما ضمن مصفوفة (أو مجموعة) من العناصر فستجد هذه القيمة في أسوأ الحالات في نهاية المصفوفة (أو لا تجدها على الإطلاق) و هذا يعني أنه إن كان عدد عناصر المصفوفة (N) عنصراً فسيبلغ تعقيد الخوارزمية الزمني (N) (لأننا نقوم يعملية وحيدة عند كل عنصر و هي المقارنة بين القيمة المطلوبة و قيمة هذا العنصر) أما إن كنا نقوم بطباعة العنصر في كل مرة نقوم بها بالمقارنة فهذا يعني (N) عملية أخرى أي يصبح تعقيد الخوارزمية (2N) .. لكن هذا الثابت لا يعني شيئاً في مجال التدوين المقارب الذي يقارب تابع التعقيد بتابع بسيط و لها ثلاثة تعابير رئيسية:

22

خوارزمية البحث التسلسلي: (O(n

خوارزمية البحث الثنائي: (O(log)(n

خوارزمية الفرز بالإدراج: (O(n2

خوارزمية الفرز بالمرج: (O(nlog)(n

و قد يظن البعض أن الفروق صغيرة بين توابع التعقيد .. لكن المفاجئ أن الفرق بين تابعين بسيطين قد يتغير بشكل دراماتيكي عندما تكبر قيم (n) لأن ذلك لا يتبع الفرق بين التابعين بقدر ما يتبع سرعة نمو كل منهما مقارنة بالآخر، و هذا شكل يوضح العملية:


حيث نلاحظ أن عمود (n) يزداد أساً عشرياً كل مرة فيما يزداد تابع (n2) أسين عشريين كل مرة، ناهيك عن التوابع الأسرع نمواً كما في الشكل التالي:


حيث أن قفزة تابع (n2) تصبح صغيرة مقارنة بتابع (n!)
أو (nn) الذين يتسارعان نمواً بشكل رهيب، و تعتبر الخوارزميات التي تعقيدها من تلك الرتب حلولاً غير صحيحة للمشاكل البرمجية التي تنمذج في النهاية عالمنا الفيزيائي حيث لا يمكننا السماح بتعاظم القيم بهذه السرعة في تطبيقات قد تشكل قضية موت أو حياة كسرعة استجابة طائرة أو أنظمة تحكم بمنشأة توليد كهرباء.

قد تكون بعض الخوارزميات التي ذكرت في الأعلى غريبة بالنسبة لك، لكن الحلقات التالية من هذه السلسلة ستخوض فيها واحدة تلو الأخرى لجعل الخوارزميات علماً شيقاً للجميع.

إعداد :Abdelraheem Ghzal

شارك المقال:

فريق الإعداد

تواصل معنا

«الباحثون المصريون» هي مبادرة علمية تطوعية تم تدشينها في 4/8/2014، بهدف إثراء المحتوى العلمي العربي، وتسهيل نقل المواد والأخبار العلمية للمهتمين بها من المصريين والعرب،

تابعنا على منصات التواصل الإجتماعي