在計算機科學中，線上算法（也叫線上算法）是能夠以串列方式逐個處理其輸入的算法，即按照輸入被饋送到算法的順序，而不是從一開始就可獲得整個輸入。
相反，離線算法從一開始就給出了整個問題數據，並且需要輸出解決手頭問題的答案。 在運籌學中，開發線上算法的領域稱為線上最佳化。
基本介紹
- 中文名：線上算法
- 外文名：Online algorithm
定義,其他解釋,例子,線上問題,
定義
因為它不知道整個輸入，所以線上算法被迫做出後來可能不是最優的決策，並且線上算法的研究關注於在這種情況下可能的決策質量。競爭分析通過比較同一問題實例的線上和離線算法的相對性能來形成這一想法。具體而言，算法的競爭比率被定義為其成本的最壞情況比除以所有可能的輸入的最優成本。線上問題的競爭比率是線上算法實現的最佳競爭比率。直觀地，算法的競爭比率給出了該算法產生的解決方案的質量的度量，而問題的競爭比率表明了解該問題的未來的重要性。
其他解釋
有關算法線上輸入的其他觀點，請參閱
流式算法：關注準確表示過去輸入所需的記憶體量;
動態算法：專注於維護線上輸入問題解決方案的時間複雜性。
例子
一些線上算法：
插入排序
感知
水庫採樣
貪心算法
對手模型
度量任務系統
賠率算法
頁面替換算法
計算方差的算法
Ukkonen的算法
線上問題
舉例說明線上算法概念的一個問題是加拿大旅行者問題。此問題的目標是最小化在加權圖中到達目標的成本，其中一些邊緣不可靠並且可能已從圖中移除。然而，只有當她/他到達邊緣的一個端點時，才會向旅行者顯示邊緣已被移除（失敗）。這個問題的最壞情況是，所有不可靠的邊緣都會失敗，問題會減少到通常的最短路徑問題。在競爭分析的幫助下，可以對問題進行替代分析。對於這種分析方法，離線算法預先知道哪些邊緣將失敗，目標是最小化線上和離線算法的性能之間的比率。這個問題是PSPACE完成的。
有許多正式問題提供了多個線上算法作為解決方案：
K伺服器問題
作業車間調度問題
列出更新問題
強盜問題
秘書問題
搜尋遊戲
滑雪租賃問題
線性搜尋問題
投資組合選擇問題
