Xiao Meng’s Blog

In computer science, an online algorithm is one that can process its input
piece-by-piece, 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. (For example,
selection sort requires that the entire list is given before it can sort it.)

As an example of the problem consider the problem of finding a shortest path in
a finite connected graph when the graph is unknown and the algorithm receives the
node neighbours only when it “enters” the node. It is clear that this problem
can not be solved optimally without a simple exhaustive search. Thus, new performance measures have to be introduced, such as
competitive analysis, which compares the performance of an
online algorithm with that of a hypothetical offline algorithm that knows the entire input in advance.

Powered by ScribeFire.