مشكلة السلف

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

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

تتمثل المشكلة في الحفاظ على مجموعة S ، التي تحتوي على مجموعة جزئية من U عدد صحيح. يمكن تخزين كل عدد من هذه الأعداد الصحيحة بحجم كلمة w ، مما يعني أن${\displaystyle U\leq 2^{w}}$تدعم هياكل البيانات التي تحل المشكلة هذه العمليات: ^{[ 2 ]}

• predecessor(x)، والتي تُرجع أكبر عنصر في S أصغر من x تمامًا
• successor(x)، والتي تُرجع أصغر عنصر في S أكبر من x بشكل صارم

بالإضافة إلى ذلك، تدعم هياكل البيانات التي تحل النسخة الديناميكية من المشكلة هذه العمليات أيضًا:

• insert(x)، مما يضيف x إلى المجموعة S
• delete(x)، مما يؤدي إلى إزالة x من المجموعة S

يتم تحليل المشكلة عادةً في نموذج حسابي ثنائي التفرع مثل ذاكرة الوصول العشوائي للكلمات .

أحد الحلول البسيطة لهذه المشكلة هو استخدام شجرة بحث ثنائية متوازنة ، والتي تحقق (في ترميز Big O ) وقت تشغيل قدره${\displaystyle O(\log n)}$بالنسبة للاستعلامات السابقة. تحقق شجرة فان إمده بواس وقت استعلام قدره${\displaystyle O(\log \log U)}$لكن ذلك يتطلب${\displaystyle O(U)}$[ ^{1 ]} اقترح دان ويلارد تحسينًا على استخدام المساحة هذا باستخدام شجرة البحث السريعة جدًا (x-fast trie) ^، والتي تتطلب${\displaystyle O(n\log U)}$المساحة ونفس وقت الاستعلام، وشجرة y-fast الأكثر تعقيدًا ، والتي تتطلب فقط${\displaystyle O(n)}$^{[ 3 ]} تحقق أشجار الاندماج ، التي قدمها مايكل فريدمان وويلارد، المساحة.${\displaystyle O(\log _{w}n)}$وقت الاستعلام و${\displaystyle O(n)}$للاستعلامات السابقة للمسألة الثابتة. ^{[ 4 ]} تم حل المسألة الديناميكية باستخدام الأشجار الأسية مع${\displaystyle O(\log _{w}n+\log \log n)}$وقت الاستعلام، ^{[ 5 ]} ومع الوقت المتوقع${\displaystyle O(\log _{w}n)}$باستخدام التجزئة . ^{[ 6 ]}

نُشرت العديد من الأبحاث التي تُثبت حدودًا دنيا لمسألة السلف، أو تُحدد زمن تشغيل الحلول المثلى تقاربًا . على سبيل المثال، أثبت مايكل بيم وفيث إيلين أنه لكل قيم w ، توجد قيمة n بزمن استعلام (في تدوين Big Theta ).${\displaystyle \Omega \left({\tfrac {\log w}{\log \log w}}\right)}$وبالمثل، لكل قيم n ، توجد قيمة لـ n بحيث يكون وقت الاستعلام هو${\displaystyle \Omega \left({\sqrt {\tfrac {\log n}{\log \log n}}}\right)}$[ ^{1 ] تشمل} البراهين الأخرى للحدود الدنيا مفهوم تعقيد الاتصال .

بالنسبة لمشكلة السلف الثابت، أظهر ميهاي باتراسكو وميكيل ثورب الحد الأدنى التالي لوقت البحث الأمثل، في نموذج مسبار الخلية : ^{[ 7 ]}$${\displaystyle O(1)\min \left\{{\begin{array}{l}\log _{w}n\\\lg {\frac {\ell -\lg n}{a}}\\{\frac {\lg {\frac {\ell }{a}}}{\lg \left({\frac {a}{\lg n}}\,\cdot \,\lg {\frac {\ell }{a}}\right)}}\\{\frac {\lg {\frac {\ell }{a}}}{\lg \left(\lg {\frac {\ell }{a}}\right/\left.\lg {\frac {\lg n}{a}}\right)}}\end{array}}\right.}$$ حيث يكون طول كلمة ذاكرة الوصول العشوائي${\displaystyle w}$، تحتوي المجموعة${\displaystyle n}$أعداد صحيحة من${\displaystyle \ell }$كل بت يتم تمثيله في ذاكرة الوصول العشوائي باستخدام${\displaystyle S}$كلمات الفضاء، وتحديدها${\displaystyle a=\lg {\frac {S}{n}}+\lg w}$.

في الحالة التي${\displaystyle w=\ell =\gamma \lg n}$ل${\displaystyle \gamma >1}$و${\displaystyle S=n\cdot \lg ^{O(1)}n}$، يكون وقت البحث الأمثل هو ${\displaystyle \Theta (\lg \ell )}$وتحقق شجرة فان إمدي بواس هذا الحد. ^{[ 7 ]}

• فرز الأعداد الصحيحة
• تجربة سريعة
• شجرة الاندماج