Qual é a maneira mais rápida de encontrar o K-menor valor em uma lista não classificada, sem classificar?

Meu algoritmo inicial:

1. Compare o elemento 0 com qualquer outro elemento, acompanhando quantos elementos são menores que ele.
2. Repita para cada elemento até encontrar um elemento maior que exatamente (k-1).

Suponho que isso levaria no pior caso. É possível obter um tempo de execução mais rápido sem classificar a lista?$O(n^2)$

Use o algoritmo de seleção para tempo linear https://en.m.wikipedia.org/wiki/Selection_algorithm

Infelizmente, não posso apenas comentar, mas tenho que publicá-lo como resposta.

De qualquer forma, você pode tentar usar um min-heap em sua matriz não classificada, conseguir uma complexidade de tempo de O (n + k * logn).

O algoritmo Quickselect pode fazer isso com O (n) complexidade média, é um dos algoritmos de seleção mais usados ​​de acordo com a Wikipedia .

É derivado do QuickSort e, como tal, sofre de uma complexidade de pior caso de O (n²) se você usar um pivô incorreto (um problema que pode ser evitado na prática).

O algoritmo em poucas palavras: após a rotação como no QuickSort, desça apenas para o lado inferior ou superior da matriz - dependendo de qual deles possui o elemento que você procura.

Crie um heap máximo de tamanho$k$. O invariante é que o heap sempre contém o$k$ menores elementos observados até agora.

1. Insira o primeiro $k$ elementos da lista na pilha
2. Para cada elemento restante $i$ na lista:
   • deixei $M$ ser o elemento máximo na pilha
   • E se $i < M$e exclua $M$ e insira $i$ na pilha

No final, o heap conterá o $k$ menores elementos da lista.

Procurar o elemento máximo tem custo constante. O custo de inserção e exclusão é$O(k)$. A complexidade do tempo desse método é$O(n . \log k)$