Алгоритм нахождения k наименьших чисел в массиве из n элементов

Question

Я пытаюсь написать алгоритм, который может печатать k наименьших чисел в массиве размера n за O (n) времени, но я не могу уменьшить сложность времени до n.Как я могу это сделать?

Answer 1

Как насчет использования кучи для хранения значений. Эта стоимость равна n, когда вы просматриваете каждое значение в массиве.

Затем пройдите кучи, чтобы получить наименьшее значение k.

Время выполнения O (n) + O (k) = O (n)

Конечно, пространство памяти теперь O (n + n)

Answer 2

Просто отсортируйте массив с помощью Merge Sort, а затем напечатайте первое число k, в худшем случае потребуется n * log2 (n).