One-pass algorithm: Difference between revisions

Revision as of 10:17, 1 July 2021

Revision as of 04:32, 8 October 2022

Line 2:

{{Refimprove|date=April 2021}}

In computing, a '''one-pass algorithm''' or '''single-pass algorithm''' is a [[streaming algorithm]] which reads its input exactly once.<ref name="frankfurt"/> It does so by processing items in order, without unbounded [[Buffer (computer science)|buffering]]; it reads a block into an [[input buffer]], processes it, and moves the result into an output buffer for each step in the process.<ref name="sjsu"/> 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.<ref name="eds"/> An example of a one-pass algorithm is the Sondik [[partially observable [[Markov decision process]].<ref name="pomdp"/>

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