الگوریتم برخط

در علوم رایانه الگوریتم بَرخط به الگوریتمی گفته می‌شود که ورودی آن به صورت دنباله‌ای از تقاضاها در دسترس الگوریتم قرار می‌گیرد. به عبارت دیگر، ورودی این الگوریتم‌ها از ابتدا در اختیار الگوریتم نیست. برای پردازش هر قطعه از ورودی، الگوریتم برخط تصمیمی غیرقابل‌ برگشت می‌گیرد.

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

توجه داشته باشید که نتیجهٔ مرتب‌سازی درجی نتیجه مطلوب یعنی لیست مرتب‌شده‌است. هرچند در بیشتر موارد، دردسترس نبودن ورودی از ابتدا کمبود بزرگی برای الگوریتم‌های برخط است و در نتیجه خروجی این الگوریتم‌ها دارای هزینهٔ بیشتر یا امتیاز کمتر نسبت به الگوریتم‌های کلاسیک است.

نمونه‌ها
برخی از الگوریتم‌های برخط:
 مرتب‌سازی درجی
 پرسپترون
 الگوریتم حریصانه
 الگوریتم جایگزینی صفحه
 الگوریتم محاسبه واریانس

جستارهای وابسته 
 رایانش بی‌درنگ

منابع

پیوند به بیرون 

 Bibliography of papers on online algorithms

الگوریتم‌های برخط