One-pass algorithm: Difference between revisions

Revision as of 05:12, 15 April 2021

Revision as of 22:48, 15 April 2021

Line 6:

{{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]]. 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>{{Citation|last=Schweikardt|first=Nicole|title=One-Pass Algorithm|datename=2009|url=https:"eds"//doi.org/10.1007/978-0-387-39940-9_253|work=Encyclopedia of Database Systems|pages=1948–1949|editor-last=LIU|editor-first=LING|place=Boston, MA|publisher=Springer US|language=en|doi=10.1007/978-0-387-39940-9_253|isbn=978-0-387-39940-9|access-date=2021-04-13|editor2-last=ÖZSU|editor2-first=M. TAMER}}</ref>

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

Line 36:

== References==

<references/>

<ref name="eds">{{Citation|last=Schweikardt|first=Nicole|title=One-Pass Algorithm|date=2009|url=https://doi.org/10.1007/978-0-387-39940-9_253|work=Encyclopedia of Database Systems|pages=1948–1949|editor-last=LIU|editor-first=LING|place=Boston, MA|publisher=Springer US|language=en|doi=10.1007/978-0-387-39940-9_253|isbn=978-0-387-39940-9|access-date=2021-04-13|editor2-last=ÖZSU|editor2-first=M. TAMER}}</ref>

<ref name="frankfurt">http://www.tks.informatik.uni-frankfurt.de/schweika/downloads/EncycDBS_OnePassAlgos.pdf</ref>

</references>

{{cs-stub}}