Difference between revisions of "Online algorithm"
Karl Jones (Talk | contribs) (Created page with "In computer science, an '''online algorithm''' is an algorithm that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input...") |
Karl Jones (Talk | contribs) (→See also) |
||
| (One intermediate revision by the same user not shown) | |||
| Line 15: | Line 15: | ||
For many problems, online algorithms cannot match the performance of [[Offline algorithm|offline algorithms]]. | For many problems, online algorithms cannot match the performance of [[Offline algorithm|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]]. | + | If the [[ratio]] between the performance of an online algorithm and an optimal offline algorithm is [[bounded]], the online algorithm is called [[Competitive analysis (online algorithm)|competitive]]. |
== Offline counterparts == | == Offline counterparts == | ||
| Line 24: | Line 24: | ||
* [[Algorithm]] | * [[Algorithm]] | ||
| + | * [[Competitive analysis (online algorithm)]] | ||
* [[Computer science]] | * [[Computer science]] | ||
* [[Offline algorithm]] | * [[Offline algorithm]] | ||
Latest revision as of 18:53, 16 May 2016
In computer science, an online algorithm is an algorithm 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.
Example: Insert sort
The insertion sort algorithm considers one input element per iteration and produces a partial solution without considering future elements.
Thus, insertion sort is an online algorithm.
By contrast, 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.
Performance
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.
Offline counterparts
Not every online algorithm has an offline counterpart.
See also
- Algorithm
- Competitive analysis (online algorithm)
- Computer science
- Offline algorithm
- Ukkonen's algorithm - online algorithm for constructing suffix trees, proposed by Esko Ukkonen in 1995
External links
- Ukkonen's algorithm @ Wikipedia
