One-pass algorithm: Difference between revisions

Revision as of 19:15, 19 November 2019

Revision as of 11:54, 25 November 2019

Line 1:

{{Unreferenced|date=January 2007}}

In computing, a '''one-pass algorithm''' is a [[streaming algorithm]] 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.

Basically one-pass algorithm operates as follows:

Line 10:

# When an object is assigned to a cluster the representative for that cluster is recomputed

# If an object fails a certain test it becomes the cluster representative of a new cluster nothing happened

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

Given any list as an input: