Encuentra el 10% más grande de los números en una matriz en orden

Question

Dando una matriz con números 'N' (N> 100). ¿Cómo podríamos encontrar el 10% más grande de ellos en orden? (si n/10 no es un número entero, podemos redondearlo)

Se me ocurrieron 3 algoritmos para intentar el problema anterior, pero no estoy seguro de cuál es el mejor en términos de tiempo de ejecución asintótico. ¿Podría hacer alguna modificación para reducir el tiempo asintótico? Además, si N es realmente grande, ¿qué algoritmo podría ser eficiente?

Estoy enumerando mis ideas para los algoritmos a continuación y realmente podría usar alguna ayuda para descubrir el algoritmo más eficiente para esto.

Algo-1

que usa la selección especie y se detuvo una vez que el 10% de los números fueron ordenadas.

Algo-2

I construyó un máximo en heap y se mantiene la eliminación de la mayor del 10% de los números

Algo-3

no han implementado esta, pero la idea que tengo es para usar cualquier algoritmo de estadística de orden para encontrar una partición que contenga el 10% superior de los números y luego ordenarlos utilizando la clasificación por fusión.

Answer 1

Si conoce N, simplemente cree una matriz con una longitud de 1/10 parte de eso. el valor inicial para cada celda es Int.MinValue. Examine cada número en la matriz. Si es más grande que el número más pequeño en la matriz del diez por ciento, agréguelo.

Evita una clasificación, pero a expensas de exploraciones constantes de la matriz de respuestas. Puede compensar esto de alguna manera manteniéndolo en orden ordenado para que pueda usar una búsqueda binaria.

Answer 2

Algo-1: La ordenación de selección se ejecutará en O (n^2). El primer escaneo que realiza (n-1) se compara, la segunda vez (n-2), el n/10 (nn/10), entonces (n-1) + (n-2) + ... + (nn/10) => O (n^2)

Algo-2: Eliminar el elemento máximo de un montón es O (log n), por lo que este ejecutará O (n log n) ya que desea eliminar n/10 elementos.

Otro algoritmo posible, aunque sigue siendo O (n log n), pero creo que podría ser mejor que Algo-2 es utilizar el siguiente procedimiento inspirado de ordenación rápida.

1. Pick a punto de pivote
2. Analiza los todos los elementos y ponerlos en uno de los 2 cubos: aquellos menor que el pivote (cubo de la izquierda) y los que mayor que el pivote (cubo derecha) (n-1) comparaciones Siga el procedimiento de ordenación rápida de intercambio en el lugar.

3. a. Tamaño del cubo en la derecha == n/10: Ya terminaste.

   b. Tamaño del cubo a la derecha> n/10, luego la nueva lista es el cubo a la derecha, recursivamente vaya al paso 1 con la nueva lista.

   c. Tamaño del cubo en el derecho < n/10, entonces la lista nueva es un cubo a la izquierda, pero solo desea encontrar el mayor n-n/10- (tamaño del cubo derecho). Recursivamente vaya al paso 1 con la nueva lista.

Answer 3

la solución más rápida es usar el partition-based selection algorithm, que se ejecuta en O(n). Se basa en la idea de quicksort, excepto que en lugar de ordenar ambas particiones recursivamente, solo vas a una de las particiones para encontrar el elemento más pequeño k-th.

Encontrar el mayor 10% se logra buscando el k=(90%*N)-th número más pequeño.

Si recuerda cómo funciona la creación de particiones en la conexión rápida, los elementos inferiores al pivote se mueven hacia la izquierda y el resto de los elementos hacia la derecha. Supongamos que desea seleccionar el elemento más pequeño k-th. Luego verá si hay al menos k elementos a la izquierda del pivote. Si hay, entonces sabes que puedes ignorar los elementos en la partición correcta. De lo contrario, puede ignorar todos los elementos en la partición izquierda, porque sabe que ese elemento estará en la partición correcta.

Tenga en cuenta que el algoritmo de selección solo identifica cuáles son los 10 mejores números. Si necesita que se clasifiquen, debe ordenar esos números (pero solo esos números, el otro 90% puede ignorarse).

Answer 4

Utilizaría quicksort descendiendo en la matriz y obtendría los primeros N/10 artículos.

Answer 5

Construya un montón con el costo de reemplazo O (lnN) lleno con los primeros n/10 elementos. Escanee los números restantes comparando con el menor valor en el montón. Si el valor del elemento actual es mayor que el elemento menor en el montón, insértelo en el montón y elimine el elemento menos. En el peor de los casos, dos operaciones O (lnN) multiplicadas por N elementos escaneados arrojan O (N ln N), que no es mejor en tiempo que una ordenación, pero requiere menos almacenamiento que ordenarlo todo, ya que en la práctica es probable que sea más rápido (especialmente si N elementos no caben en la memoria caché, pero n/10 lo hará; el tiempo asintótico solo le importa a uno que se encuentre en un espacio plano).

Answer 6

El algoritmo más eficaz sería utilizar una oferta rápida modificada.

Quicksort comienza seleccionando un valor "medio" y colocando todos los valores más bajos que este a la izquierda, y todos mayores a la derecha. Normalmente descenderías y ordenarías recursivamente ambos lados, pero solo necesitas ordenar el lado derecho si hay menos del 10% de los elementos a la izquierda.

Si hay más del 10%, solo necesita ordenar el lado izquierdo, y probablemente solo el lado izquierdo.

Esto no reducirá la complejidad por debajo del O óptimo (N lg N), pero reducirá el factor constante y lo hará más rápido que el obvio "sistema rápido luego elija el primer acercamiento de 10".

Answer 7

Pregunta muy tonta, simplemente ordene con cualquier algoritmo de clasificación, y tome los primeros N/10 artículos.

Algo-2 es equivalente a hacer esto con el montón-tipo

Answer 8

porque esta es la tarea, mi respuesta sería cualquier algoritmo de clasificación, esto se debe a que no puede resolver esto bajo O (n * log (n))

si esto fuera posible, entonces podría ordenar completamente una matriz bajo O (n * log (n)). (al encontrar el 10% superior clasificado en la matriz que desea ordenar completamente, eliminándolos y repitiendo este proceso 10 veces).

porque la ordenación no es posible en O (n * log (n)), por lo que es este problema.