خوازمية موضعية

في المعلوماتية النظرية، الخوارزمية الموضعية بالأنجليزية (In-Place Algorithm): أو خوارزمية الترتيب بذات المكان الذاكري عبارة عن خوارزمية تقوم بتحويل المدخلات باستخدام أي بنية بيانات مساعدة. باستخدام قدر صغير من مساحة الذاكرة الإضافية للمتغيرات المساعدة. عادة ما يتم الكتابة فوق المدخلات بالمخرجات أثناء تنفيذ الخوارزمية. تقوم الخوارزمية الموضعية بتحديث تسلسل الإدخال الخاص بها فقط من خلال استبدال العناصر أو تبديلها. أحيانًا تسمى الخوارزمية not-in-place أوout-of-place.

يمكن أن يكون للموضع معاني مختلفة قليلاً. في أكثر أشكالها صرامة، لا يمكن أن تحتوي الخوارزمية إلا على مقدار ثابت من المساحة الإضافية، مع احتساب كل شيء بما في ذلك استدعاءات الوظائف Functions والمؤشرات Pointers. ومع ذلك، فإن هذا النموذج محدود للغاية لأن وجود فهرس لطول n يتطلب بتات O (log n). على نطاق أوسع، تعني كلمة in-place أن الخوارزمية لا تستخدم مساحة إضافية لمعالجة المدخلات ولكنها قد تتطلب مساحة إضافية صغيرة وإن كانت غير ثابتة لتشغيلها. عادةً ما تكون هذه المساحة هي O (log n)، على الرغم من السماح أحيانًا بأي شيء في O (n). حيث يلاحظ أن تعقيد الفضاء الذاكري له أيضًا خيارات متنوعة في ما إذا كان سيتم حساب أطوال الفهرس أم لا كجزء من المساحة المستخدمة. في كثير من الأحيان، يتم إعطاء التعقيد المكاني من حيث عدد المؤشرات أو المؤشرات المطلوبة، مع تجاهل طولها. في هذه المقالة، نشير إلى إجمالي تعقيد الفضاء (DSPACE)، مع حساب أطوال المؤشر. لذلك، تحتوي متطلبات المساحة هنا على عامل تسجيل n إضافي مقارنة بتحليل يتجاهل طول المؤشرات والمؤشرات.

قد تحسب الخوارزمية أو لا تحسب الإخراج كجزء من استخدامها للمساحة. نظرًا لأن الخوارزميات الموضعية عادةً ما تستبدل مدخلاتها بالإخراج، فلا حاجة إلى مساحة إضافية. عند كتابة الإخراج في ذاكرة الكتابة فقط أو التدفق، قد يكون من الأنسب مراعاة مساحة عمل الخوارزمية فقط. في التطبيقات النظرية مثل تخفيض مساحة السجل، يكون من المعتاد تجاهل مساحة الإخراج دائمًا (في هذه الحالات يكون من الضروري أن يكون الإخراج للكتابة فقط write-only).