One-pass algorithm: Difference between revisions

Revision as of 22:46, 14 October 2007

Revision as of 12:58, 16 May 2009

Line 1:

In computing, a '''one-pass algorithm''' is one which reads its input exactly once, in order, without unbounded [[Buffer (computer science)|buffering]]. A one-pass algorithm generally requires O(n) (see [[Big O Notation|'big O' notation]]) time and less than O(n) storage (typically O(1)), where n is the size of the input.

===Example problems solvable by one-pass algorithms===

Given any list as an input:

* Count the number of elements.

Line 17:

* Find the maximum gap between two appearances of a given symbol.

===Example problems not solvable by one-pass algorithms===

Given any list as an input:

* Find the middle element of the list.

Line 23:

Given a list of numbers:

* Find the [[median]].

* Find the [[mode (statistics)|modemodes]]s (This is not the same is finding the most frequent symbol from a limited alphabet).

* Sort the list.