¿Cuál es la forma más rápida de encontrar el valor Kth más pequeño en una lista sin ordenar sin ordenar?

Mi algoritmo inicial:

1. Compare el elemento 0 con cualquier otro elemento, haciendo un seguimiento de cuántos elementos son menores.
2. Repita para cada elemento hasta que se encuentre un elemento que sea mayor que exactamente (k-1).

Supongo que esto tomaría en el peor de los casos. ¿Se puede lograr un tiempo de ejecución más rápido sin ordenar la lista?$O(n^2)$

Use el algoritmo de selección para tiempo lineal https://en.m.wikipedia.org/wiki/Selection_algorithm

Desafortunadamente no puedo comentar, pero tengo que publicarlo como respuesta.

De todos modos, podría intentar usar un montón mínimo en su matriz no ordenada, debería poder obtener una complejidad de tiempo de O (n + k * logn).

El algoritmo Quickselect puede hacer eso en O (n) complejidad promedio, es uno de los algoritmos de selección más utilizados según Wikipedia .

Se deriva de QuickSort y, como tal, sufre una complejidad O (n²) en el peor de los casos si utiliza un pivote incorrecto (un problema que se puede evitar en la práctica).

El algoritmo en pocas palabras: después de pivotar como en QuickSort, solo desciende hacia el lado inferior o superior de la matriz, dependiendo de cuál de ellos tiene el elemento que estás buscando.

Crea un montón de tamaño máximo$k$. Lo invariable es que el montón siempre contiene$k$ elementos más pequeños observados hasta ahora.

1. Insertar el primero $k$ elementos de la lista en el montón
2. Para cada elemento restante $i$ en la lista:
   • dejar $M$ ser el elemento máximo en el montón
   • Si $i < M$, luego borre $M$ e inserte $i$ en el montón

Al final, el montón contendrá el $k$ elementos más pequeños en la lista.

Buscar el elemento máximo tiene un costo constante. El costo de inserción y eliminación es$O(k)$. La complejidad temporal de este método es$O(n . \log k)$