Dado:
- mil millones de números en una matriz sin clasificar
- una garantía de que solo hay 1000 números diferentes, y
- algunos supuestos sobre la frecuencia relativa
entonces podemos usar un algoritmo probabilístico que se ejecuta con una “pequeña constante” en relación con el número de elementos de entrada.
- Elige un número aleatorio de la matriz
- Agréguelo a un conjunto.
- Si el conjunto tiene 1000 elementos, finalice e imprima el resultado.
- De lo contrario, regrese al paso 1
Es posible que desee vincular el número de muestras en la práctica e informar un error, o cambiar a un algoritmo más lento pero determinista, si se requieren demasiadas muestras.
Suponga que cada número aparece al menos 1000 veces (una frecuencia de 0.0001%). Para hacer un análisis del peor de los casos, asumiremos que aparecen 999 números con una frecuencia mínima y el otro ocupa todo el resto. Como estimación aproximada, podemos decir que la probabilidad de encontrar un nuevo número en cada prueba es de aproximadamente [matemática] 10 ^ {- 6} [/ matemática]. (Obviamente, es más alto que eso, pero no pude encontrar una manera simple de hacer los cálculos en este momento; la mayoría de los ejemplos de este tipo de problema solo se refieren al caso uniforme).
- ¿Cuál es el programa más simple para encontrar números primos en C ++?
- ¿Cuál es la complejidad de [matemáticas] T (n) = 2T (n-1) + C? [/ Matemáticas]
- ¿Existe una aplicación de Android que toma datos de entrada y genera una ecuación algebraica?
- ¿Cuál es el cálculo más simple para que un número crezca pero a incrementos más pequeños a medida que aumenta?
- Cómo demostrar que en un torneo round-robin, no más de la mitad de los equipos pueden compartir la puntuación más alta
Eso significa que, después de las pruebas [matemática] K [/ matemática], habremos encontrado todos los números con probabilidad aproximadamente [matemática] 1- (1-10 ^ {- 6}) ^ K [/ matemática].
[matemáticas] K = 10000 [/ matemáticas]: menos del 1%
[matemática] K = 10 ^ 5 [/ matemática]: menos del 9.5%
[matemáticas] K = 10 ^ 6 [/ matemáticas]: aproximadamente 63%
[matemáticas] K = 10 ^ 7 [/ matemáticas]: aproximadamente 99.99%
Entonces, después de muestrear al menos el 1% de los cubos, es casi seguro que habremos encontrado las 1000 entradas, incluso si la mayoría de ellas son raras.
Si en cambio asumiéramos una distribución uniforme, ¡solo necesitaríamos unas 50,000 muestras! Por lo tanto, el tiempo de ejecución esperado está determinado por las propiedades de la distribución, en lugar de estrictamente por el tamaño de entrada.