Algoritmo de una sola pasada

En informática, un algoritmo de una sola pasada es un algoritmo de flujo que lee su entrada exactamente una vez. ^{[ 1 ]} 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. ^{[ 2 ]} Un algoritmo de una sola pasada generalmente requiere un tiempo de O ( n ) (véase la notación 'big O' ) y un almacenamiento menor a O ( n ) (típicamente O (1)), donde n es el tamaño de la entrada. ^{[ 3 ]} Un ejemplo de un algoritmo de una sola pasada es el proceso de decisión de Markov parcialmente observable de Sondik . ^{[ 4 ]}

Dada cualquier lista como entrada:

• Cuenta el número de elementos.

Dada una lista de números:

• Encuentra los k elementos más grandes o más pequeños, donde k se da de antemano.
• Calcula la suma , la media , la varianza y la desviación estándar de los elementos de la lista. Consulta también Algoritmos para calcular la varianza .

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

• Cuenta el número de veces que aparece cada símbolo en la entrada.
• Encuentra los elementos más o menos frecuentes.
• Ordena la lista según algún orden en los símbolos (posible ya que el número de símbolos posteriores es limitado).
• Encuentra la máxima diferencia entre dos apariciones de un símbolo dado.

Dada cualquier lista como entrada:

• Encuentra el enésimo elemento desde el final (o informa que la lista tiene menos de n elementos).
• Encuentra el elemento central de la lista. Sin embargo, esto se puede resolver en dos pasos: el paso 1 cuenta los elementos y el paso 2 selecciona el del medio.

Dada una lista de números:

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

Los algoritmos de dos pasadas mencionados anteriormente siguen siendo algoritmos de transmisión continua , pero no algoritmos de una sola pasada.