El algoritmo de Marzullo , inventado por Keith Marzullo para su tesis doctoral en 1984, es un algoritmo de acuerdo utilizado para seleccionar fuentes para estimar el tiempo preciso a partir de una serie de fuentes de tiempo ruidosas . Una versión refinada de este algoritmo, rebautizada como " algoritmo de intersección ", forma parte del moderno Protocolo de Tiempo de Red . El algoritmo de Marzullo también se utiliza para calcular la intersección relajada de n cajas (o, de manera más general, n subconjuntos de R n ), como lo requieren varios métodos de estimación de conjuntos robustos .
El algoritmo de Marzullo es eficiente en términos de tiempo para producir un valor óptimo a partir de un conjunto de estimaciones con intervalos de confianza donde el valor real puede estar fuera del intervalo de confianza para algunas fuentes. En este caso, se considera que la mejor estimación es el intervalo más pequeño que sea consistente con el mayor número de fuentes.
Si tenemos las estimaciones 10 ± 2, 12 ± 1 y 11 ± 1, entonces estos intervalos son [8,12], [11,13] y [10,12] que se intersecan para formar [11,12] o 11,5 ± 0,5, lo que es consistente con los tres valores.
Si, en cambio, los rangos son [8,12], [11,13] y [14,15], entonces no hay ningún intervalo consistente con todos estos valores, pero [11,12] es consistente con el mayor número de fuentes, es decir, dos de ellas.
Finalmente, si los rangos son [8,9], [8,12] y [10,12] entonces ambos intervalos [8,9] y [10,12] son consistentes con el mayor número de fuentes.
Este procedimiento determina un intervalo. Si el resultado deseado es el mejor valor de ese intervalo, entonces un enfoque ingenuo sería tomar el centro del intervalo como valor, que es lo que se especificó en el algoritmo Marzullo original. Un enfoque más sofisticado reconocería que esto podría estar descartando información útil de los intervalos de confianza de las fuentes y que un modelo probabilístico de las fuentes podría devolver un valor distinto del centro.
Tenga en cuenta que el valor calculado probablemente se describa mejor como "optimista" en lugar de "óptimo". Por ejemplo, considere tres intervalos [10,12], [11, 13] y [11,99,13]. El algoritmo descrito a continuación calcula [11,99, 12] o 11,995 ± 0,005, que es un valor muy preciso. Si sospechamos que una de las estimaciones puede ser incorrecta, entonces al menos dos de las estimaciones deben ser correctas. Bajo esta condición, la mejor estimación es [11,13] ya que este es el intervalo más grande que siempre interseca al menos dos estimaciones. El algoritmo descrito a continuación se parametriza fácilmente con el número máximo de estimaciones incorrectas.
El algoritmo de Marzullo comienza preparando una tabla de las fuentes, ordenándola y luego buscando (de manera eficiente) las intersecciones de los intervalos. Para cada fuente hay un rango [c−r,c+r] definido por c ± r. Para cada rango, la tabla tendrá dos tuplas de la forma ⟨offset,type⟩ . Una tupla representará el comienzo del rango, marcado con tipo −1 como ⟨c−r,−1⟩ y la otra representará el final con tipo +1 como ⟨c+r,+1⟩ .
La descripción del algoritmo utiliza las siguientes variables: best (mayor número de intervalos superpuestos encontrados), cnt (número actual de intervalos superpuestos), beststart y bestend (el comienzo y el final del mejor intervalo encontrado hasta el momento), i (un índice) y la tabla de tuplas.
El algoritmo de Marzullo es eficiente tanto en el espacio como en el tiempo. El uso asintótico del espacio es O(n) , donde n es el número de fuentes. Al considerar el requisito de tiempo asintótico, se puede considerar que el algoritmo consiste en construir la tabla, ordenarla y buscarla. La ordenación se puede realizar en un tiempo O(n log n) , y esto domina las fases de construcción y búsqueda que se pueden realizar en un tiempo lineal . Por lo tanto, la eficiencia temporal del algoritmo de Marzullo es O(n log n) .
Una vez que se ha creado y ordenado la tabla, es posible actualizar el intervalo de una fuente (cuando se recibe nueva información) en tiempo lineal. Por lo tanto, la actualización de los datos de una fuente y la búsqueda del mejor intervalo se pueden realizar en tiempo O(n).