C #: Algoritmo eficiente para encontrar los mejores elementos m en una matriz N x N

Question

Me gustaría saber si hay un algoritmo eficiente para encontrar los mejores elementos m en una matriz N x N, con un encabezado de método como este:

double[] greatestValues(double[][] matrix, int numberOfElements);

¿Alguna idea?

Answer 1

Si trata la matriz N x N como una matriz de elementos N x N, puede aplicar una de las siguientes técnicas:

  

Aplicación directa del algoritmo de selección basado en ordenación rápida   el algoritmo de selección basado en la clasificación puede ser   solía encontrar k más pequeño o k más grande   elementos. Para encontrar k elementos más pequeños   encontrar el késimo elemento más pequeño usando   la mediana de las medianas clasificación rápida basada   algoritmo. Después de la partición que   encuentra el késimo elemento más pequeño, todos   los elementos más pequeños que el kth   elemento más pequeño estará presente a la izquierda   al elemento k y todos los elementos   más grande estará presente directamente a la   k elemento más pequeño. Así todo   elementos del 1 ° al elemento k   inclusive constituyen el k más pequeño   elementos. La complejidad del tiempo es   lineal en n, el número total de   elementos.

     

Soluciones basadas en estructura de datos Otro método simple es agregar cada   elemento de la lista en un orden   establecer la estructura de datos, como un montón o   árbol de búsqueda binaria autoequilibrante,   con a lo sumo k elementos. Siempre que   estructura de datos tiene más de k   elementos, eliminamos el más grande   elemento, que se puede hacer en O (log k)   hora. Cada operación de inserción también   toma tiempo O (log k), lo que resulta en   O (nlog k) tiempo general.

     

Es posible transformar la lista   en un montón en & # 920; (n) tiempo, y luego   atravesar el montón utilizando una modificación   Primero algoritmo de búsqueda que   coloca los elementos en una prioridad   Cola (en lugar de la cola ordinaria   que normalmente se usa en un BFS), y   terminar el escaneo después de atravesar   exactamente k elementos Como el tamaño de la cola   permanece O (k) durante todo el recorrido,   requeriría tiempo O (klog k) para   completa, lo que lleva a un límite de tiempo de   O (n + klog k) en este algoritmo.

De aquí .