Algoritmo de una pasada - One-pass algorithm

En informática, un algoritmo de un solo paso o un algoritmo de un solo paso es un algoritmo de transmisión que lee su entrada exactamente una vez. Lo hace procesando los elementos en orden, sin almacenamiento en búfer ilimitado ; lee un bloque en un búfer de entrada , lo procesa y mueve el resultado a un búfer de salida para cada paso del proceso. Un algoritmo de una pasada generalmente requiere O ( n ) (ver notación 'gran O' ) tiempo y menos de O ( n ) almacenamiento (típicamente O (1)), donde n es el tamaño de la entrada. Un ejemplo de un algoritmo de un solo paso es el proceso de decisión de Markov parcialmente observable de Sondik .

Problemas de ejemplo que se pueden resolver mediante algoritmos de un paso

Dada cualquier lista como entrada:

  • Cuente el número de elementos.

Dada una lista de números:

Dada una lista de símbolos de un alfabeto de k símbolos, dada de antemano.

  • Cuente el número de veces que aparece cada símbolo en la entrada.
  • Encuentra los elementos más o menos frecuentes.
  • Ordene la lista de acuerdo con algún orden en los símbolos (posible ya que el número de símbolos es limitado).
  • Encuentre el espacio máximo entre dos apariencias de un símbolo dado.

Problemas de ejemplo que no se pueden resolver con algoritmos de una sola pasada

Dada cualquier lista como entrada:

  • Encuentre el n- ésimo elemento desde el final (o informe que la lista tiene menos de n elementos).
  • Encuentra el elemento del medio de la lista. Sin embargo, esto se puede solucionar con dos pasadas: la pasada 1 cuenta los elementos y la pasada 2 elige la del medio.

Dada una lista de números:

  • Encuentra la mediana .
  • Encontrar los modos (esto no es lo mismo que encontrar el símbolo más frecuente de un alfabeto limitado).
  • Ordena la lista.
  • Cuente el número de elementos mayor o menor que la media . Sin embargo, esto se puede hacer en la memoria constante con dos pasadas: la pasada 1 encuentra el promedio y la pasada 2 hace el conteo.

Los algoritmos de dos pasos anteriores siguen siendo algoritmos de transmisión, pero no algoritmos de un solo paso.

Referencias

  1. ^ Schweikardt, Nicole. "Algoritmo de una pasada" (PDF) . Consultado el 1 de julio de 2021 .
  2. Pollett, Chris (14 de marzo de 2005). "Algoritmos de uno y dos pasos" (PDF) . Consultado el 1 de julio de 2021 .
  3. ^ Schweikardt, Nicole (2009), LIU, LING; ÖZSU, M. TAMER (eds.), "Algoritmo de un solo paso" , Encyclopedia of Database Systems , Boston, MA: Springer US, págs. 1948-1949, doi : 10.1007 / 978-0-387-39940-9_253 , ISBN 978-0-387-39940-9, consultado el 13 de abril de 2021
  4. ^ "Algoritmo de un paso de Sondik" . www.pomdp.org .