Quel est le moyen le plus rapide pour trouver la plus petite valeur Kth dans une liste non triée sans tri?

Mon algorithme initial:

1. Comparez l'élément 0 avec tous les autres éléments, en gardant une trace du nombre d'éléments qui lui sont inférieurs.
2. Répétez l'opération pour chaque élément jusqu'à ce qu'un élément supérieur à exactement (k-1) soit trouvé.

Je suppose que cela prendrait $O(n^2)$au pire des cas. Peut-on obtenir un temps d'exécution plus rapide sans trier la liste?

Utiliser l'algorithme de sélection pour le temps linéaire https://en.m.wikipedia.org/wiki/Selection_algorithm

Malheureusement, je ne peux pas simplement commenter mais je dois le poster comme réponse.

Quoi qu'il en soit, vous pouvez essayer d'utiliser un segment min sur votre tableau non trié, vous devriez pouvoir obtenir une complexité temporelle de O (n + k * logn).

L'algorithme Quickselect peut le faire dans une complexité moyenne O (n), c'est l'un des algorithmes de sélection les plus utilisés selon Wikipedia .

Il est dérivé de QuickSort et souffre en tant que tel d'une complexité O (n²) dans le pire des cas si vous utilisez un mauvais pivot (un problème qui peut être évité dans la pratique).

L'algorithme en bref: après le pivotement comme dans QuickSort, ne descendez que dans le côté inférieur ou supérieur du tableau - selon lequel d'entre eux a l'élément que vous recherchez.

Créer un tas max de taille$k$. L'invariant est que le tas contient toujours le$k$ les plus petits éléments observés jusqu'à présent.

1. Insérez le premier $k$ éléments de la liste dans le tas
2. Pour chaque élément restant $i$ dans la liste:
   • laisser $M$ être l'élément maximum dans le tas
   • Si $i < M$, puis supprimez $M$ et insérer $i$ dans le tas

À la fin, le tas contiendra le $k$ les plus petits éléments de la liste.

La recherche de l'élément maximal a un coût constant. Le coût d'insertion et de suppression est$O(k)$. La complexité temporelle de cette méthode est$O(n . \log k)$