One-pass algorithm

One-pass algorithm

In computing, a one-pass algorithm is one which reads its input exactly once, in order, without unbounded buffering. A one-pass algorithm generally requires O(n) (see '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.
  • Find the nth element (or report that the list has fewer than n elements).
  • Find the nth element from the end (or report that the list has fewer than n elements).

Given a list of numbers:

Given a list of symbols from an alphabet of k symbols, given in advance.

  • Count the number of times each symbol appears in the input.
  • Find the most or least frequent elements.
  • Sort the list according to some order on the symbols (possible since the number of symbols is limited).
  • 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.

Given a list of numbers:

  • Find the median.
  • Find the modes (This is not the same is finding the most frequent symbol from a limited alphabet).
  • Sort the list.

Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • One-time pad — Excerpt from a one time pad In cryptography, the one time pad (OTP) is a type of encryption, which has been proven to be impossible to crack if used correctly. Each bit or character from the plaintext is encrypted by a modular addition with a bit …   Wikipedia

  • Sorting algorithm — In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most used orders are numerical order and lexicographical order. Efficient sorting is important for optimizing the use of other… …   Wikipedia

  • GSP Algorithm — ( Generalized Sequential Pattern algorithm) is an algorithm used for sequence mining. The algorithms for solving sequence mining problems are mostly based on the a priori (level wise) algorithm. One way to use the level wise paradigm is to first… …   Wikipedia

  • Three-pass protocol — In cryptography, the three pass protocol for sending messages is a framework which allows one party to securely send a message to a second party without the need to exchange or distribute encryption keys. This message protocol should not be… …   Wikipedia

  • Cartan-Karlhede algorithm — One of the most fundamental problems of Riemannian geometry is this: given two Riemannian manifolds of the same dimension, how can one tell if they are locally isometric? This question was addressed by Elwin Christoffel, and completely solved by… …   Wikipedia

  • Page replacement algorithm — This article is about algorithms specific to paging. For outline of general cache algorithms (e.g. processor, disk, database, web), see Cache algorithms. In a computer operating system that uses paging for virtual memory management, page… …   Wikipedia

  • Rete algorithm — The Rete algorithm is an efficient pattern matching algorithm for implementing production rule systems. The Rete algorithm was designed by Dr Charles L. Forgy of Carnegie Mellon University, first published in a working paper in 1974, and later… …   Wikipedia

  • Forward-backward algorithm — In computer science, the forward backward algorithm, a dynamic programming algorithm for computing the probability of a particular observation sequence, given the parameters of the model, operates in the context of hidden Markov models. Overview… …   Wikipedia

  • Low-pass filter — A low pass filter is a filter that passes low frequency signals but attenuates (reduces the amplitude of) signals with frequencies higher than the cutoff frequency. The actual amount of attenuation for each frequency varies from filter to filter …   Wikipedia

  • Knuth–Morris–Pratt algorithm — The Knuth–Morris–Pratt string searching algorithm (or KMP algorithm) searches for occurrences of a word W within a main text string S by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”