Hola estoy tratando de entender cómo la mediana deEl algoritmo de las medianas funciona. En todos los ejemplos que he visto hasta ahora, ya hay grupos de números divididos, antes de que comience la ejecución del algoritmo. Por lo tanto, no puedo entender cómo se forman estos grupos. Para ser más específicos en los ejemplos estudiados hasta ahora, se afirma que hay 9 grupos de 5 números cada uno, por ejemplo, alias 45 números, o 4 grupos de 10 números también conocidos como 40 números. Entonces, ¿qué pasa si tenemos n números ...? ¿Hay alguna buena técnica que deba seguir para encontrar el ¿Cuántos elementos debería tener su grupo?
Respuestas
1 para la respuesta № 1MoM es un algoritmo recursivo. Existe como una forma sólida de seleccionar un "pivote" para un algoritmo como quicksort o quickselect. Por lo tanto, necesita operar dentro de ciertos límites de tiempo.
Podría ser más fácil de entender si se explica como un caso base y un caso recursivo.
El caso base es suficientemente claro. Si tiene menos de cinco elementos en una lista, entonces encuentra la mediana de manera ingenua.
Pero, si su lista tiene al menos cinco elementos,Se puede aplicar el caso recursivo. Vas a tomar grupos sucesivos de cinco elementos de tu lista grande, encontrar su mediana y agregarlos a una lista más pequeña. (Si te sobran algunos, puedes ignorarlos).
Si esta nueva lista más pequeña es lo suficientemente pequeña,Puede aplicar el caso base, como se describe anteriormente. De lo contrario, irá a la lista "pequeña" para crear otra lista aún más pequeña. Haga espuma, enjuague y repita hasta que quede menos de cinco elementos restantes. Y esa es su estimación de la mediana general. Así que funciona con cualquier tamaño de lista.
Entonces, ¿qué tan grande debe ser "cinco"? Bueno, resulta que 5 es óptimo. Alguien mostró el análisis de complejidad en la página de Wikipedia para este tema. Esencialmente, los valores más grandes de "cinco" le dan una mejor aproximación de la mediana al costo de más trabajo para encontrar la mediana de "cinco". Desafortunadamente, 3 no disminuye el espacio de búsqueda lo suficiente por iteración para ser una opción valiosa de "cinco". Y, por lo general, debe ser extraño, a menos que desee gastar ciclos dividiendo la diferencia entre elementos.