خوارزمية فورية
من ويكيبيديا، الموسوعة encyclopedia
في علم الحاسوب، الخوارزمية الفورية (online algorithm[1]) هي التي تقوم بمعالجة المدخلات (أو البيانات) عن طريق إدراجها عنصر تلو الأخر بطريقة تسلسلية، أي أن ترتيب المدخلات يكون على حسب ظهورها بشكل فوري إلى الخوارزمية، دون أن تكون جميع المدخلات متاحة منذ البداية.
هذه مقالة غير مراجعة. (مايو 2020) |
على النقيض من ذلك، يتم إعطاء الخوارزمية الغير فورية مدخلات المشكلة بأكملها من البداية، وعلى الخوارزمية أن تجد الحل المناسب للمشكلة الكاملة. في أبحاث العمليات، يسمى المجال الذي يتم فيه دراسة وتطوير الخوارزميات الفورية بالتحسين الفوري (أو الأمثلية الفورية).
لنأخذ على سبيل المقارنة خوارزميتين الترتيب بالإنتقاء والإدراج: الترتيب بالانتقاء يوجد العنصر الأقل قيمة من الباقي الغير المصنف ويضعه في أول القائمة، هذا الأمر يتطلب الوصول إلى جميع العناصر بأكملها؛ مما يجعل هذه الخوارزمية غير فورية. من ناحية أخرى، الترتيب بالإدراج يأخذ بعين الاعتبار عنصر واحد فقط في كل تكرار. وفي كل تكرار، الخوارزمية تزيل عنصرًا واحدًا من البيانات المتاحة وتجد الموقع الذي ينتمي إليه ضمن القائمة المصنفة. وبذلك الخوارزمية تنتج حلاً جزئيًا دون النظر إلى العناصر المستقبلية في كل تكرار، مما يجعل هذه الخوارزمية فورية.
لاحظ أن الترتيب بالإدراج يعطي النتيجة المثلى، أي قائمة عناصر مرتبة بشكل صحيح تماماً. ولكن بالنسبة للعديد من المسائل الرياضية، لا يمكن أن تجاري الخوارزميات الفورية أداء الخوارزميات الغير فورية. إذا كانت النسبة بين أداء الخوارزمية الفورية ونظيرتها الغير الفورية (المثلى) محدودة بثابت، فإن الخوارزمية الفورية تعتبر تنافسية.[1]
ليس لكل خوارمية غير فورية نظير فعال (تنافسي) فوري.