الگوریتم برخط
در علوم رایانه الگوریتم بَرخط[۱] به الگوریتمی گفته می‌شود که ورودی آن به صورت دنباله‌ای از تقاضاها در دسترس الگوریتم قرار می‌گیرد. به عبارت دیگر، ورودی این الگوریتم‌ها از ابتدا در اختیار الگوریتم نیست. برای پردازش هر قطعه از ورودی، الگوریتم برخط تصمیمی غیرقابل برگشت می‌گیرد.
به عنوان نمونه دو گونه مرتب‌سازی انتخابی و مرتب‌سازی درجی را در نظر بگیرید. الگوریتم مرتب‌سازی انتخابی به تناوب کوچک‌ترین عضو زیرمجموعهٔ نامرتب را انتخاب و در مکان مناسب زیرمجموعه مرتب شده اضافه می‌کند. درمقابل، مرتب‌سازی درجی عناصر مجموعه اولیه را یکی‌یکی در نظر گرفته و هر عضو را در مکان مناسب درمیان عناصر پیشتر درنظرگرفته شده قرار می‌دهد، به‌گونه‌ای که عناصری که تا به حال در نظر گرفته شده‌اند زیرمجموعه‌ای مرتب را تشکیل دهند. از آنجا که مرتب‌سازی درجی عناصر مجموعه را یکی‌یکی پردازش می‌کند می‌توان این الگوریتم را یک الگوریتم برخط تلقی کرد.
توجه داشته باشید که نتیجهٔ مرتب‌سازی درجی نتیجه مطلوب یعنی لیست مرتب‌شده‌است. هرچند در بیشتر موارد، دردسترس نبودن ورودی از ابتدا کمبود بزرگی برای الگوریتم‌های برخط است و در نتیجه خروجی این الگوریتم‌ها دارای هزینهٔ بیشتر یا امتیاز کمتر نسبت به الگوریتم‌های کلاسیک است.[۱]
نمونه‌ها
[ویرایش]برخی از الگوریتم‌های برخط:
جستارهای وابسته
[ویرایش]منابع
[ویرایش]- ↑ ۱٫۰ ۱٫۱ 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. Archived from the original (PDF) on 5 March 2016. Retrieved 17 August 2015.