خوارزمية في مكانها

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

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

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

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

دالة عكسية(أ[0..ن - 1]) تخصيص b[0..n - 1] لكل i من 0 إلى n - 1 b[n − 1 − i] := a[i] أعد b

لسوء الحظ، يتطلب هذا مساحة إضافية قدرها O ( n ) لتخزين المصفوفات aو bفي آنٍ واحد. كما أن تخصيص الذاكرة وإلغاء تخصيصها عمليتان بطيئتان في كثير من الأحيان. وبما أننا لم نعد بحاجة إلى a، يمكننا بدلاً من ذلك استبدالها بعكسها باستخدام هذه الخوارزمية الموضعية التي لن تحتاج إلا إلى عدد ثابت (2) من الأعداد الصحيحة للمتغيرات المساعدة iو tmp، بغض النظر عن حجم المصفوفة.

دالة reverse_in_place(a[0..n-1]) for i from 0 to floor((n-2)/2) tmp := a[i] a[i] := a[n − 1 − i] a[n − 1 − i] := tmp

كمثال آخر، تقوم العديد من خوارزميات الفرز بإعادة ترتيب المصفوفات في مكانها لترتيبها الصحيح، بما في ذلك: فرز الفقاعات ، وفرز المشط ، وفرز التحديد ، وفرز الإدراج ، وفرز الكومة ، وفرز شل . لا تتطلب هذه الخوارزميات سوى عدد قليل من المؤشرات، لذا فإن تعقيدها المكاني هو O (log n ) . ^{[ 1 ]}

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

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

يمكن تنفيذ بعض خوارزميات معالجة النصوص مثل القص والعكس في مكانها.

في نظرية التعقيد الحسابي ، يشمل التعريف الدقيق للخوارزميات الموضعية جميع الخوارزميات ذات التعقيد المكاني O (1) ، أي فئة DSPACE (1). هذه الفئة محدودة للغاية؛ فهي تُعادل اللغات المنتظمة . ^{[ 2 ]} في الواقع، لا تشمل أيًا من الأمثلة المذكورة أعلاه.

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

إن ربط الخوارزميات الموضعية بالرمز L له دلالات مهمة؛ فعلى سبيل المثال، يعني ذلك وجود خوارزمية موضعية (معقدة نوعًا ما) لتحديد ما إذا كان هناك مسار بين عقدتين في رسم بياني غير موجه ، ^{[ 3 ]} وهي مشكلة تتطلب مساحة إضافية قدرها O ( n ) باستخدام خوارزميات تقليدية مثل البحث العميق أولًا (بت زيارة لكل عقدة). وهذا بدوره يُنتج خوارزميات موضعية لمسائل مثل تحديد ما إذا كان الرسم البياني ثنائي الأجزاء أو اختبار ما إذا كان لرسمين بيانيين نفس عدد المكونات المتصلة .

في كثير من الحالات، يمكن تقليل متطلبات المساحة للخوارزمية بشكل كبير باستخدام خوارزمية عشوائية . على سبيل المثال، إذا أردنا معرفة ما إذا كان رأسان في رسم بياني مكون من n رأسًا يقعان في نفس المكون المتصل من الرسم البياني، فلا توجد خوارزمية بسيطة وحتمية ومحددة مسبقًا لتحديد ذلك. مع ذلك، إذا بدأنا ببساطة من رأس واحد وقمنا بمسح عشوائي لحوالي 20n³ خطوة، فإن احتمال عثورنا على الرأس الآخر، بشرط أن يكون في نفس المكون، يكون مرتفعًا جدًا. وبالمثل، توجد خوارزميات عشوائية بسيطة ومحددة مسبقًا لاختبار أولية الأعداد، مثل اختبار ^ميلر -رابين ، كما توجد أيضًا خوارزميات تحليل عوامل عشوائية بسيطة ومحددة مسبقًا، مثل خوارزمية بولارد رو .

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

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

• جدول خوارزميات الفرز الموضعي وغير الموضعي