¿Cuál es la desventaja del algoritmo ingenuo de muestreo aleatorio simple?
Se han desarrollado varios algoritmos eficientes para el muestreo aleatorio simple Un algoritmo ingenuo es el algoritmo sorteo a sorteo, en el que en cada paso eliminamos el elemento de ese paso del conjunto con igual probabilidad y lo introducimos en la muestra. Continuamos hasta tener una muestra del tamaño deseado
�
k. El inconveniente de este método es que requiere un acceso aleatorio en el conjunto.

El algoritmo de selección-rechazo desarrollado por Fan et al. en 1962 requiere una sola pasada sobre los datos; sin embargo, es un algoritmo secuencial y requiere conocer el recuento total de elementos
�
n, que no está disponible en escenarios de streaming.

Sunter demostró en 1977 un algoritmo de ordenación aleatoria muy sencillo, que simplemente asigna un número aleatorio extraído de una distribución uniforme
(
0
,
1
)
(0,1) como clave para cada elemento, luego ordena todos los elementos utilizando la clave y selecciona el más pequeño
�
k más pequeño.

J. Vitter propuso en 1985 los algoritmos de muestreo de reservorio, que se utilizan ampliamente. Este algoritmo no requiere conocer el tamaño de la población
�
n de antemano, y utiliza un espacio constante.

El muestreo aleatorio también se puede acelerar tomando muestras de la distribución de huecos entre muestras y saltándose los huecos.
El inconveniente de este método es que requiere un acceso aleatorio en el conjunto.