الگوریتم برخط
در علوم رایانه الگوریتم بَرخط به الگوریتمی اطلاق میشود که ورودی آن به صورت دنبالهای از تقاضاها در دسترس الگوریتم قرار میگیرد. به عبارت دیگر، ورودی این الگوریتمها از ابتدا در اختیار الگوریتم نیست. برای پردازش هر قطعه از ورودی، الگوریتم برخط تصمیمی غیرقابلبرگشت میگیرد.
به عنوان نمونه، دو گونه مرتبسازی انتخابی و مرتبسازی درجی را در نظر بگیرید. الگوریتم مرتبسازی انتخابی به تناوب کوچکترین عضو زیرمجموعهٔ نامرتب را انتخاب و در مکان مناسب زیرمجموعه مرتبشده اضافه میکند. درمقابل، مرتبسازی درجی عناصر مجموعه اولیه را یکییکی در نظر گرفته و هر عضو را در مکان مناسب درمیان عناصر پیشتر درنظرگرفته شده قرار میدهد، بهگونهای که عناصری که تابهحال در نظر گرفته شدهاند زیرمجموعهای مرتب را تشکیل دهند. از آن جا که مرتبسازی درجی عناصر مجموعه را یکییکی پردازش میکند، میتوان این الگوریتم را یک الگوریتم برخط تلقی کرد.
توجه داشته باشید که نتیجهٔ مرتبسازی درجی نتیجه مطلوب یعنی لیست مرتبشدهاست. هرچند در بیشتر موارد، دردسترس نبودن ورودی از ابتدا کمبود بزرگی برای الگوریتمهای برخط است و در نتیجه خروجی این الگوریتمها دارای هزینهٔ بیشتر یا امتیاز کمتر نسبت به الگوریتمهای کلاسیک است.
نمونهها
برخی از الگوریتمهای برخط:
جستارهای وابسته
منابع
- ↑ Karp, Richard M. (1992). "On-line algorithms versus off-line algorithms: How much is it worth to know the future?" (PDF). IFIP Congress (1). 12: 416–429. Retrieved 17 August 2015.