موضوع مقاله: الگوریتم درجا | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم درجا | مقدمه: الگوریتم درجا در علم کامپیوتر الگوریتمی است که ورودی را با استفاده از یک داده ساختار با یک حافظهٔ اضافی کوچک و ثابت تبدیل می‌کند. | ## بخش 1: الگوریتم درجا | ورودی معمولاً به وسیلهٔ خروجی که هنگام اجرای الگوریتم به وجود می‌آید، دوباره نوشته می‌شود. یک الگوریتم تا زمانی به‌طور رسمی درجا نامیده می‌شود که ورودی به وسیله خروجی بازنویسی شود. در واقع این شرط نه کافی است (در مواردی که داده‌ها به‌طور مرتب نمایش داده شده) و نه لازم است; ممکن است فضای داده خروجی ثابت باشد یا حتی ممکن است قابل شمارش نباشد؛ برای مثال در حالتی که خروجی در (گردش) جریان باشد. ازسوی دیگر، گاهی اوقات ممکن است عملی تر باشد که فضای داده خروجی را حساب کنیم، تا تعیین کنیم که آیا این الگوریتم درجا است یا نه. مانند مثال اول معکوس زیر؛ این باعث می‌شود که تعریف کردن الگوریتمهای درجا به شدت مشکل شود. در کاربردهای نظری مانند کاهش فضای ورود، همیشه از فضای داده‌های خروجی چشم پوشی می‌شود. اکثر الگوریتم انتخابها نیز درجا هستند، اگرچه بعضی از آن‌ها به‌طور قابل ملاحظه‌ای دادهٔ ورودی آرایه را در فرایند یافتن نتیجه نهایی با اندازهٔ ثابت، بازآرایی می‌کنند. | ## بخش 2: الگوریتم درجا | برخی از الگوریتم‌های دستکاری متن مانند اصلاح شده و معکوس ممکن است درجا انجام شوند. پیچیدگی محاسباتی در نظریه پیچیدگی محاسباتی، الگوریتمهای درجا شامل همهٔ الگوریتمهای با پیچیدگی فضایی ، کلاس پیچیدگی فضا هستند. به همین دلیل، ما نیز الگوریتم‌های L را مطرح می‌کنیم، کلاس این مسائل به فضای اضافی نیاز دارند تا درجا باشند. اگرچه به نظر می‌رسد که با تعریف قبلی ما در تناقض است، ما باید فرض کنیم که در جهان انتزاعی ورودی ما می‌تواند به‌طور قراردادی بزرگ باشد. بر روی یک کامپیوتر واقعی، یک اشاره گر فقط به یک مقدار فضای ثابت و کوچک نیاز دارد. چون مقدار حافظهٔ فیزیکی محدود است، اما به‌طور کلی بیت نیاز است تا اندیس را در لیستی با سایز n مشخص کند. از لحاظ فنی، این به فضا نیاز دارد، از آنجایی که هر یک از چارچوب پشته شامل تعداد ثابتی اشاره گر هستند. | ## بخش 3: الگوریتم درجا | (سایز هر کدام از آن‌ها است.) شناسایی الگوریتمهای درجا با L دارای مفاهیم جالبی است؛ به‌طور مثال، به این معنی است که الگوریتمهای درجای (نسبتاً پیچیده) وجود دارند که تعیین می‌کنند آیا یک مسیر بین دو گره در یک گراف بدون جهت وجود دارد یا نه.Omer Reingold. نقش تصادفی در بسیاری از موارد، فضای مورد نیاز برای یک الگوریتم می‌تواند با استفاده از الگوریتم تصادفی به شدت کاهش یابد. به عنوان مثال، می‌خواهیم بدانیم دو راس درون یک گراف n راسی در یک مؤلفهٔ همبند گراف هستند. الگوریتم درجای ساده شناخته شده‌ای به صورت قطعی برای تعیین این موضوع وجود ندارد، ولی اگر ما به سادگی از یک راس شروع کنیم و به‌طور تصادفی با گام بر روی رئوس پیش برویم، شانس اینکه به راسی که آن را از قبل انتخاب کرده‌ایم برسیم و این دو در یک مولفه همبندی باشند، بالا می‌رود. آن‌ها اغلب الگوریتمهای درجایی که داده‌ها را بازنویسی می‌کنند، به‌طور صریح پشتیبانی نمی‌کنند، از این رو این یک نوع اثر زیان‌آور است؛ در عوض، آن‌ها فقط اجازه می‌دهند داده‌های جدید ساخته شود. با این حال، کامپایلرهای زبان‌های تابعی خوب اغلب زمانی که یک شیء ساخته شده بسیار شبیه به شیء موجود باشد، تشخیص می‌دهند و سپس شیء قدیمی توسط آن‌ها دور انداخته می‌شود و این به یک جهش ساده "under-the-hood" بهینه سازی می‌شود. | ## جمع‌بندی | توجه داشته باشید که ممکن است در اصل برای به دقت ساختن الگوریتمهای درجایی که داده‌ها را تغییر نمی‌دهند (مگر این که داده‌ها دیگر مورد استفاده قرار نگرفته باشند) ولی این در عمل به ندرت انجام می‌شود.