مشكلة تمييز العناصر

في نظرية التعقيد الحسابي ، تُعرف مشكلة تمييز العناصر أو مشكلة تفرد العناصر بأنها مشكلة تحديد ما إذا كانت جميع عناصر القائمة متميزة.

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

تم إثبات العديد من الحدود الدنيا في التعقيد الحسابي عن طريق اختزال مشكلة تمييز العناصر إلى المشكلة قيد البحث، أي عن طريق إثبات أنه يمكن إيجاد حل مشكلة تفرد العناصر بسرعة بعد حل المشكلة قيد البحث.

عدد المقارنات اللازمة لحل مشكلة الحجم${\displaystyle n}$، في نموذج حسابي قائم على المقارنة مثل شجرة القرار أو شجرة القرار الجبرية ، هو${\displaystyle \Theta (n\log n)}$. هنا،${\displaystyle \Theta }$يستخدم هذا الأسلوب ترميز ثيتا الكبير ، مما يعني أنه يمكن حل المشكلة في عدد من المقارنات يتناسب مع${\displaystyle n\log n}$( دالة خطية لوغاريتمية ) وأن جميع الحلول تتطلب هذا العدد من المقارنات. ^{[ 2 ]} في نماذج الحساب هذه، لا يمكن استخدام أرقام الإدخال لفهرسة ذاكرة الحاسوب (كما في حل جدول التجزئة)، بل يمكن الوصول إليها فقط عن طريق حساب ومقارنة دوال جبرية بسيطة لقيمها. بالنسبة لهذه النماذج، تحل خوارزمية قائمة على فرز المقارنة المشكلة ضمن عامل ثابت لأفضل عدد ممكن من المقارنات. وينطبق الحد الأدنى نفسه أيضًا على العدد المتوقع للمقارنات في نموذج شجرة القرار الجبرية العشوائية . ^{[ 3 ] [ 4 ]}

إذا كانت عناصر المسألة أعدادًا حقيقية ، فإن الحد الأدنى لشجرة القرار يمتد إلى نموذج آلة الوصول العشوائي الحقيقية مع مجموعة تعليمات تتضمن جمع وطرح وضرب الأعداد الحقيقية، بالإضافة إلى المقارنة والقسمة أو الباقي ("التقريب إلى أقرب عدد صحيح"). ^{[ 5 ]} ويترتب على ذلك أن تعقيد المسألة في هذا النموذج هو أيضًا${\displaystyle \Theta (n\log n)}$يغطي نموذج ذاكرة الوصول العشوائي هذا خوارزميات أكثر من نموذج شجرة القرار الجبرية، إذ يشمل الخوارزميات التي تستخدم الفهرسة في الجداول. مع ذلك، في هذا النموذج، تُحتسب جميع خطوات البرنامج، وليس القرارات فقط.

يمكن لآلة تورينج حتمية أحادية الشريط حل المشكلة، لـ n عنصرًا من m ≥ log n بت لكل منها، في وقت O ( n ² m ( m +2–log n )) ، بينما على آلة غير حتمية يكون التعقيد الزمني O ( nm ( n + log m )) . ^{[ 6 ]}

يمكن للخوارزميات الكمومية حل هذه المشكلة بشكل أسرع، في${\textstyle \Theta (n^{2/3})}$الاستفسارات. الخوارزمية المثلى من ابتكار أندريس أمباينيس . ^{[ 7 ]} أثبت ياويون شي لأول مرة حدًا أدنى دقيقًا عندما يكون حجم النطاق كبيرًا بما فيه الكفاية. ^{[ 8 ]} قام أمباينيس ^{[ 9 ]} وكوتين ^{[ 10 ]} بشكل مستقل (وعبر براهين مختلفة) بتوسيع عمله للحصول على الحد الأدنى لجميع الدوال.

العناصر التي تحدث أكثر من${\displaystyle n/k}$مرات في مجموعة متعددة الحجم${\displaystyle n}$يمكن العثور عليها بواسطة خوارزمية تعتمد على المقارنة، وهي خوارزمية ميسرا-غريس للضربات القوية ، في الوقت المناسب${\displaystyle O(n\log k)}$تُعدّ مشكلة تمييز العناصر حالة خاصة من هذه المشكلة حيث${\displaystyle k=n}$. هذا الوقت هو الأمثل في ظل نموذج شجرة القرار للحساب. ^{[ 11 ]}

• مشكلة التصادم