¿Cuál es el algoritmo más eficiente para encontrar el késimo elemento más pequeño en una matriz que tiene n elementos desordenados?

Lo que está buscando se llama estadística de orden [matemática] k [/ matemática].

Hay algunos algoritmos para resolver esto en tiempo lineal (tanto determinista como no determinista). Esos algoritmos son:

• Selección rápida
• Mediana de medianas (también conocida como BFPRT)
• Introselect
• Algoritmo sin nombre usando montones suaves

Selección rápida
Quickselect es un algoritmo aleatorio que resuelve el problema en el tiempo esperado [matemático] O (n) [/ matemático]. Quickselect es una adaptación del algoritmo de clasificación rápida.

Más información: http://en.wikipedia.org/wiki/Qui …

Mediana de medianas (BFPRT)
El algoritmo de mediana de medianas resuelve el problema de manera determinista en [math] \ Theta (n) [/ math] time. Sin embargo, el valor constante para el algoritmo de mediana de medianas es bastante alto.

Más información: http://en.wikipedia.org/wiki/Med …

Introselect
El algoritmo de introselección comienza usando la selección rápida, pero tan pronto como se desvía de las operaciones O (n), por defecto usa el algoritmo de mediana de medianas, asegurando el peor tiempo de ejecución de [matemáticas] \ Theta (n )[/mates].

Más información: http://en.wikipedia.org/wiki/Int …

Algoritmo sin nombre usando montones suaves
Este algoritmo de selección implica insertar y eliminar elementos de un montón dinámico y se ejecuta de manera determinista en tiempo [matemático] \ Theta (n) [/ matemático].

Más información: http://en.wikipedia.org/wiki/Sof …

—————————————–

Para referencia:
http://en.wikipedia.org/wiki/Sel …
estadísticas de orden k

¡Hola!

Este programa está en java para Determinar k elemento más pequeño en una matriz sin clasificar .

  import java.util.Scanner;

 clase pública KthSmallestElement {

	
 public static void main (String [] args) {
		 Scanner sc = nuevo escáner (System.in);
		 System.out.print ("Ingrese tamaño:");
		 int n = sc.nextInt ();
		
		 int a [] = nuevo int [n];
		 para (int i = 0; i  = k)
			 {
				 mientras que (a [i]  x)
					 j--;
				 int t = a [i];
				 a [i] = a [j];
				 a [j] = t;
				 i ++;
				 j--;
			 }
			 si (j  k)
				 u = j;
		 }
		
	
	 System.out.println ("kth Elemento más pequeño:" + a [k]);
	 sc.close ();
	 }

 }

Hay dos formas de hacerlo, dependiendo de la disponibilidad de memoria, puede elegir una.
Primero es usar la ordenación rápida donde, según la posición de pivote después de cada iteración, sabemos cuántos elementos son más pequeños que el pivote y son mayores que él. Según la posición del pivote, buscamos a la izquierda o derecha del pivote el k-ésimo elemento más pequeño. Este método funciona cuando podemos traer todos los elementos en la memoria a la vez.
Encuentra el elemento Kth más pequeño en la matriz: aplicación de ordenación rápida

El segundo método es usar montones. Cree un montón máximo de elementos K y luego verifique cada elemento, si es mayor que la raíz del montón, saque la raíz y agregue un nuevo elemento al montón. Una vez que hayamos terminado con todos los elementos, nos quedaremos con k elementos más pequeños.
Montones: Encuentra el elemento K más pequeño de una matriz dada

Construir un montón mínimo = Θ (n)
Eliminar elementos superiores (k-1) veces del montón = O ((k-1) log n)
Entonces, el tiempo total = Θ (n) + O ((k-1) log n) = O (n + k.logn) = O (n)

Hay muchas soluciones O (n log (n)), pero a veces si los elementos de la matriz son distintos, resolver este problema en O (max (arr [i]) – min (arr [i])) será lo suficientemente rápido .

Definirá una matriz booleana llamada encontrado con un tamaño igual a max (arr [i]) – min (arr [i]) + 1 y con valores iniciales de false y tendrá una variable llamada offset = -min (arr [ i]), luego realizará un bucle en los elementos de matriz dados y para cada elemento x establecerá encontrado [x + offset] = verdadero. Entonces tendrá otro ciclo para devolver el valor Y – desplazamiento donde Y es K-ésimo encontrado [i] como verdadero.

Encuentra Kth más pequeño con K = N / 2.
Aplique la lógica de partición del algoritmo de clasificación rápida para resolver este problema.
Seleccione un pivote y colóquelo en el lugar correcto en el índice J usando la lógica de partición.
Si J = K devuelve el elemento Jth.
Si K De lo contrario, resuelva el segundo subproblema de forma recursiva.

Cree un montón con todos los números y elimine la mitad de los números del montón. El siguiente número como raíz en el árbol será la mediana. (si el número de números es impar, entonces hay una mediana, de lo contrario dos medianas, lo que supongo que debería entenderse).

Usar el algoritmo de selección #Median_selection_as_pivot_strategy