خوارزمية مثالية تقاربياً

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

بصورة أكثر رسمية، تكون الخوارزمية مثالية تقاربياً بالنسبة لمورد معين إذا ثبت أن المشكلة تتطلب Ω( f ( n )) من ذلك المورد، وثبت أن الخوارزمية تستخدم فقط O ( f ( n )).

تتطلب هذه البراهين افتراض نموذج معين للحساب ، أي قيود معينة على العمليات المسموح بها مع بيانات الإدخال.

كمثال بسيط، من المعروف أن جميع خوارزميات فرز المقارنة تتطلب على الأقل Ω( n log n ) مقارنة في المتوسط ​​وفي أسوأ الحالات. تُعدّ خوارزميتا فرز الدمج وفرز الكومة من خوارزميات فرز المقارنة التي تُجري O ( n log n ) مقارنة، لذا فهما مثاليتان تقاربياً بهذا المعنى.

إذا كانت بيانات الإدخال تتمتع ببعض الخصائص المسبقة التي يمكن استغلالها في بناء الخوارزميات، بالإضافة إلى المقارنات، فقد يكون من الممكن تطوير خوارزميات أسرع تقاربياً. على سبيل المثال، إذا عُلم أن العناصر N هي أعداد صحيحة (ليس بالضرورة مختلفة) من النطاق [1، N ]، فيمكن فرزها في زمن O ( N ) ، على سبيل المثال، باستخدام خوارزمية فرز الدلو .

من نتائج كون الخوارزمية مثالية تقاربياً أنه، بالنسبة للمدخلات الكبيرة بما يكفي، لا يمكن لأي خوارزمية أخرى أن تتفوق عليها بأكثر من عامل ثابت. لهذا السبب، غالباً ما يُنظر إلى الخوارزميات المثالية تقاربياً على أنها "نهاية المطاف" في البحث، أي الوصول إلى نتيجة لا يمكن تحسينها بشكل كبير. في المقابل، إذا لم تكن الخوارزمية مثالية تقاربياً، فهذا يعني أنه مع ازدياد حجم المدخلات، يصبح أداء الخوارزمية أسوأ بشكل متزايد من أفضل الخوارزميات الممكنة.

من المفيد عمليًا البحث عن خوارزميات ذات أداء أفضل، حتى وإن لم تتمتع بأي ميزة تقاربية. قد تُقدم الخوارزميات الجديدة مزايا أخرى، مثل الأداء الأفضل على مدخلات محددة، أو تقليل استخدام موارد أخرى، أو سهولة وصفها وتنفيذها. لذا، فإن الخوارزميات المثلى تقاربيًا ليست دائمًا هي "النهاية".

على الرغم من أن الخوارزميات المثلى تقاربياً تُعد نتائج نظرية مهمة، إلا أنه قد لا يتم استخدام الخوارزمية المثلى تقاربياً في عدد من المواقف العملية:

• إنها تتفوق فقط على الطرق الأكثر شيوعًا المستخدمة لـ n خارج نطاق أحجام الإدخال العملية، مثل المدخلات التي تحتوي على عدد بتات أكثر مما يمكن أن يتسع له أي نظام تخزين حاسوبي .
• إنها معقدة للغاية، لدرجة أن صعوبة فهمها وتنفيذها بشكل صحيح تفوق فائدتها المحتملة في نطاق أحجام المدخلات قيد الدراسة.
• تندرج المدخلات التي يتم مواجهتها في الممارسة العملية ضمن حالات خاصة تحتوي على خوارزميات أكثر كفاءة أو يمكن للخوارزميات الاستدلالية ذات أوقات الحالة الأسوأ السيئة حلها بكفاءة.
• في الحواسيب الحديثة، قد تُصبح تحسينات الأجهزة ، مثل ذاكرة التخزين المؤقت والمعالجة المتوازية ، غير فعّالة عند استخدام خوارزمية مثالية تقاربياً (بافتراض أن التحليل لم يأخذ هذه التحسينات في الحسبان). في هذه الحالة، قد توجد خوارزميات دون المستوى الأمثل تستغل هذه الميزات بشكل أفضل وتتفوق على الخوارزمية المثلى عند استخدام بيانات واقعية.

من الأمثلة على الخوارزميات المثلى تقاربياً والتي لا تُستخدم عملياً خوارزمية برنارد شازيل الخطية لتثليث مضلع بسيط . مثال آخر هو بنية بيانات المصفوفة القابلة لتغيير الحجم المنشورة في "المصفوفات القابلة لتغيير الحجم في الوقت والمساحة الأمثلين" ^{[ 1 ]} ، والتي يمكن فهرسة عناصرها في وقت ثابت، ولكنها تُسبب عبئاً عملياً كبيراً على العديد من الأجهزة مقارنةً بفهرسة المصفوفات العادية.

بصورة رسمية، لنفترض أن لدينا نظرية الحد الأدنى التي تُبين أن حل مسألة ما يتطلب زمنًا قدره Ω( f ( n )) لحالة (مدخل) بحجم n (انظر ترميز Big O §  ترميز Big Omega لتعريف Ω). عندئذٍ، يُقال إن الخوارزمية التي تحل المسألة في زمن قدره O ( f ( n )) هي خوارزمية مثالية تقاربياً.

على الرغم من أن الخوارزمية عادة ما يتم تطبيقها على كفاءة الوقت، إلا أنه يمكن القول إنها تستخدم المساحة المثلى تقاربياً، أو البتات العشوائية، أو عدد المعالجات، أو أي مورد آخر يتم قياسه عادة باستخدام ترميز Big O.

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

يُطلق على عدم وجود خوارزمية مثالية تقاربياً اسم تسريع الأداء. تُبين نظرية بلوم لتسريع الأداء وجود مسائل مصطنعة تتضمن تسريع الأداء. مع ذلك، يبقى السؤال مطروحاً حول ما إذا كانت العديد من الخوارزميات الأكثر شهرة اليوم مثالية تقاربياً أم لا. على سبيل المثال، هناك...${\displaystyle O(n\alpha (n))}$خوارزمية لإيجاد الأشجار الممتدة الدنيا ، حيث${\displaystyle \alpha (n)}$هي الدالة العكسية لدالة أكرمان ، والتي تنمو ببطء شديد ، ولكن أفضل حد أدنى معروف هو الحد الأدنى البسيط.${\displaystyle \Omega (n)}$لا يُعرف ما إذا كانت هذه الخوارزمية مثالية تقاربياً، ومن المرجح أن يُعتبر التوصل إلى حلٍّ لها إنجازاً هاماً. وقد أثبت كوبرسميث ووينوغراد (1982) أن ضرب المصفوفات يتمتع بنوعٍ ضعيف من تسريع العمليات ضمن فئة محدودة من الخوارزميات (متطابقات ستراسن الثنائية الخطية مع حساب لامدا).

• مشكلة تفرد العنصر
• التعقيد الحسابي التقاربي