الگوریتم درجا

فرض کنید می‌خواهیم آرایه ای n رقمی را معکوس کنیم یکی از راه‌های ساده این است که:

function reverse(a[0..n])
     allocate b[0..n]
     for i from 0 to n
         b[n - i] = a[i]
     return b

متأسفانه، در اینجا به ${\displaystyle (n)O}$

function reverse-in-place(a[0..n])
     for i from 0 to floor(n/2)
         swap(a[i], a[n-i])

به عنوان مثالی دیگر، تعدادی الگوریتم مرتب سازی هستند که می‌توانند آرایه‌ها را به آرایه‌های درجا مرتب شده بازآرایی کنند، از جمله: مرتب‌سازی حبابی، مرتب‌سازی شانه‌ای، مرتب‌سازی انتخابی، مرتب‌سازی درجی، مرتب‌سازی هرمی و مرتب‌سازی شِل.

مرتب‌سازی سریع معمولاً به عنوان الگوریتم درجا تعریف می‌شود. ولی در واقع یکی نیست. اکثر پیاده سازی‌ها نیازمند ${\displaystyle (ngol)O}$

اکثر الگوریتم انتخابها نیز درجا هستند، اگرچه بعضی از آن‌ها به‌طور قابل ملاحظه‌ای دادهٔ ورودی آرایه را در فرایند یافتن نتیجه نهایی با اندازهٔ ثابت، بازآرایی می‌کنند.

برخی از الگوریتم‌های دستکاری متن مانند اصلاح شده و معکوس ممکن است درجا انجام شوند.

در نظریه پیچیدگی محاسباتی، الگوریتمهای درجا شامل همهٔ الگوریتمهای با پیچیدگی فضایی ${\displaystyle (1)O}$

به همین دلیل، ما نیز الگوریتم‌های L را مطرح می‌کنیم، کلاس این مسائل به فضای اضافی ${\displaystyle (logn)O}$

آیا به این معنی است که مرتب‌سازی سریع یک الگوریتم درجا است؟ هرگز. از لحاظ فنی، این به${\displaystyle (n^{l}og2)O}$

شناسایی الگوریتمهای درجا با L دارای مفاهیم جالبی است؛ به‌طور مثال، به این معنی است که الگوریتمهای درجای (نسبتاً پیچیده) وجود دارند که تعیین می‌کنند آیا یک مسیر بین دو گره در یک گراف بدون جهت وجود دارد یا نه. مشکل این است که به ${\displaystyle (n)O}$

در بسیاری از موارد، فضای مورد نیاز برای یک الگوریتم می‌تواند با استفاده از الگوریتم تصادفی به شدت کاهش یابد. به عنوان مثال، می‌خواهیم بدانیم دو راس درون یک گراف n راسی در یک مؤلفهٔ همبند گراف هستند. الگوریتم درجای ساده شناخته شده‌ای به صورت قطعی برای تعیین این موضوع وجود ندارد، ولی اگر ما به سادگی از یک راس شروع کنیم و به‌طور تصادفی با ${\displaystyle {}^{3}n02}$

زبانهای برنامه نویسی تابعی گاهی دلسردکننده‌است. آن‌ها اغلب الگوریتمهای درجایی که داده‌ها را بازنویسی می‌کنند، به‌طور صریح پشتیبانی نمی‌کنند، از این رو این یک نوع اثر زیان‌آور است؛ در عوض، آن‌ها فقط اجازه می‌دهند داده‌های جدید ساخته شود. با این حال، کامپایلرهای زبان‌های تابعی خوب اغلب زمانی که یک شیء ساخته شده بسیار شبیه به شیء موجود باشد، تشخیص می‌دهند و سپس شیء قدیمی توسط آن‌ها دور انداخته می‌شود و این به یک جهش ساده "under-the-hood" بهینه سازی می‌شود.

توجه داشته باشید که ممکن است در اصل برای به دقت ساختن الگوریتمهای درجایی که داده‌ها را تغییر نمی‌دهند (مگر این که داده‌ها دیگر مورد استفاده قرار نگرفته باشند) ولی این در عمل به ندرت انجام می‌شود. ساختمان داده‌های تابعی را ببینید.

 http://en.wikipedia.org/wiki/In-place_algorithm

• Table of in-place and not-in-place algorithms