Найти n минимальных значений в массиве C

Question

Мне просто интересно узнать о наиболее эффективный алгоритм.

Answer 1

В O(n): Вы можете использовать selection algorithm, чтобы найти 5 самых маленьких элементов в 5 * O(n) = O(n) время. На практике, однако, более эффективен следующий метод:

В O(nlogn): сортируйте массив (используя любой из нескольких алгоритмов, которые работают в O(nlogn) времени), а затем просто посмотрите на первые пять элементов.

Хотя решение O(n) выбора асимптотический предпочтительнее O(nlogn) сортировочного раствора, на практике из-за очень большие скрытые константы в алгоритме O(n) выбора, сортировки массива будет быстрее.