top-k самый большой элемент из максимальной кучи

Я студент-механик, и я изменил свою область на компьютеры. Нужно пройти курс алгоритмов. Этот вопрос является одним из вопросов упражнения

  1. Если время работы алгоритма максимальной кучи равно O(klogn), то есть ли какой-либо алгоритм, который имеет лучшее время работы, чем этот?

performance algorithm max-heap
person user2798432    schedule 20.09.2013    source источник
comment
как я уже сказал, время работы O (klogn), но есть ли какой-либо алгоритм, который имеет лучшее время работы?   -  person user2798432    schedule 20.09.2013

Ответы (1)


arrow_upward
2
arrow_downward

  1. Распечатать и удалить корень k раз;
  2. O(k log n);
  3. Да.
person IVlad    schedule 20.09.2013
comment
не могли бы вы сказать мне, какой алгоритм будет лучше и какое время работы для этого? - person user2798432; 20.09.2013
comment
@user2798432 - O(k log k) будет лучше, это описано в моей ссылке. - person IVlad; 20.09.2013