Online algorithm
In computer science, an online algorithm is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start. In contrast, an offline algorithm is given the whole problem data from the beginning and is required to output an answer which solves the problem at hand. In operations research, the area in which online algorithms are developed is called online optimization. Not every offline algorithm has an efficient online counterpart.
- Comment
- enIn computer science, an online algorithm is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start. In contrast, an offline algorithm is given the whole problem data from the beginning and is required to output an answer which solves the problem at hand. In operations research, the area in which online algorithms are developed is called online optimization. Not every offline algorithm has an efficient online counterpart.
- DifferentFrom
- Offline
- Online
- Has abstract
- enIn computer science, an online algorithm is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start. In contrast, an offline algorithm is given the whole problem data from the beginning and is required to output an answer which solves the problem at hand. In operations research, the area in which online algorithms are developed is called online optimization. As an example, consider the sorting algorithms selection sort and insertion sort: selection sort repeatedly selects the minimum element from the unsorted remainder and places it at the front, which requires access to the entire input; it is thus an offline algorithm. On the other hand, insertion sort considers one input element per iteration and produces a partial solution without considering future elements. Thus insertion sort is an online algorithm. Note that the final result of an insertion sort is optimum, i.e., a correctly sorted list. For many problems, online algorithms cannot match the performance of offline algorithms. If the ratio between the performance of an online algorithm and an optimal offline algorithm is bounded, the online algorithm is called competitive. Not every offline algorithm has an efficient online counterpart.
- Is primary topic of
- Online algorithm
- Label
- enOnline algorithm
- Link from a Wikipage to an external page
- www.cs.technion.ac.il/~rani/book.html
- www.cs.ucr.edu/~marek/pubs/online.bib
- Link from a Wikipage to another Wikipage
- Adversary (online algorithm)
- Algorithm
- Algorithms for calculating variance
- Bandit problem
- Canadian Traveller Problem
- Category:Online algorithms
- Competitive analysis (online algorithm)
- Computer science
- Dynamic algorithm
- Greedy algorithm
- Insertion sort
- Job shop scheduling
- K-server problem
- Linear search problem
- List update problem
- Metrical task systems
- Odds algorithm
- Offline learning
- Online machine learning
- Online optimization
- Operations research
- Page replacement algorithm
- Perceptron
- Prophet inequality
- PSPACE-complete
- Real-time computing
- Reservoir sampling
- Search games
- Secretary problem
- Selection sort
- Sequential algorithm
- Shortest path problem
- Ski rental problem
- Sorting algorithms
- Streaming algorithm
- Ukkonen's algorithm
- SameAs
- 4583199-3
- 4wfd8
- Algorithme online
- Algoritmo online
- Algorytm online
- m.05ph2
- Online algorithm
- Online-Algorithmus
- Online-algoritme
- Online-algoritmi
- Q786431
- Thuật toán trực tuyến
- Онлайн алгоритм
- אלגוריתם מקוון
- الگوریتم برخط
- خوارزمية فورية
- ขั้นตอนวิธีออนไลน์
- オンラインアルゴリズム
- 線上演算法
- 온라인 알고리즘
- Subject
- Category:Online algorithms
- WasDerivedFrom
- Online algorithm?oldid=1094612724&ns=0
- WikiPageLength
- 5611
- Wikipage page ID
- 22716
- Wikipage revision ID
- 1094612724
- WikiPageUsesTemplate
- Template:Cite book
- Template:Confuse
- Template:Reflist
- Template:Short description