خوارزمية المؤشر

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

استُخدم هذا النموذج على نطاق واسع في حلّ المشكلات المتعلقة ببنية بيانات المجموعات المنفصلة . فعلى سبيل المثال، استخدم تارجان ولا بوتري هذا النموذج لإثبات حدود دنيا للتعقيد المُستهلك لبنية بيانات المجموعات المنفصلة ^{[ 1 ] [ 2 ]} (كما تناول لا بوتري مشكلة البحث عن تقسيم الفترات ). واستخدم بلوم هذا النموذج لإثبات حد أدنى لوقت أسوأ حالة لعملية واحدة لبنية بيانات المجموعات المنفصلة ^{[ 3 ]} . كما أثبت بلوم وروشو حدًا أدنى لأسوأ حالة لمشكلة البحث عن اتحاد الفترات ^{[ 4 ] .}

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

• تحافظ الخوارزمية على بنية مترابطة من العقد.
• يرتبط كل عنصر من عناصر المشكلة بعقدة.
• يتم تمثيل كل مجموعة بعقدة.
• تشكل عقد كل مجموعة مكونًا متصلًا مميزًا في الهيكل (تسمى هذه الخاصية قابلية الفصل ).
• يتم تنفيذ عملية البحث عن طريق اتباع الروابط من عقدة العنصر إلى عقدة المجموعة.

في ظل هذه الافتراضات، فإن الحد الأدنى لـ${\displaystyle \Omega (m\alpha (m,n))}$تم إثبات أن ذلك يتعلق بتكلفة سلسلة من m عملية.