Sí, si estamos dispuestos a aceptar una probabilidad de error no trivial en nuestra respuesta.
Muestra aleatoriamente 300 (o 100, o 500) elementos de la matriz. Si esta muestra no tiene un elemento mayoritario, responda “no”. De lo contrario, responda “sí”.
El costo de la operación de muestreo y conteo mayoritario es O (1), con un factor constante muy grande. Pero consume aproximadamente la misma cantidad de tiempo si la matriz tiene 100, 1000 o 1000000 elementos. (Suponiendo un modelo de acceso uniforme, de todos modos).
- ¿En qué se diferencia la ramificación y el límite del retroceso?
- ¿Cuál es el promotor y algoritmo SEO más importante en 2017?
- ¿Cuál es la sobrecarga máxima en el algoritmo de relleno de bytes?
- Cómo mejorar en la implementación de algoritmos
- ¿Cómo funciona este algoritmo para encontrar el máximo común divisor (MCD)?
La parte difícil es determinar qué tan probable es que te equivoques. Veamos un caso límite como un ejemplo (consulte a su estadístico local para obtener las fórmulas generales). Supongamos que tenemos un millón de elementos y la mayoría es solo 500,001. Usemos un tamaño de muestra de 100. Entonces, la probabilidad de que nuestra muestra contenga al menos 51 de la mayoría es igual a 1 – la función de distribución acumulativa hasta 50 de la distribución Binomial con p = 0.500001 ([matemática] 1 – F (50 ; 100, 500001/1000000) [/ math]) que es aproximadamente 46%. Le irá mejor si la mayoría no está tan cerca del 50%.
