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:
- Encuentre los k elementos más grandes o más pequeños, k dados de antemano.
- Encuentre la suma , media , varianza y desviación estándar de los elementos de la lista. Consulte también Algoritmos para calcular la varianza .
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
- ^ Schweikardt, Nicole. "Algoritmo de una pasada" (PDF) . Consultado el 1 de julio de 2021 .
- ↑ Pollett, Chris (14 de marzo de 2005). "Algoritmos de uno y dos pasos" (PDF) . Consultado el 1 de julio de 2021 .
- ^ 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
- ^ "Algoritmo de un paso de Sondik" . www.pomdp.org .