Можно ли это приблизить?

Question

Сложность времени нахождения k наибольшего элемента с использованием min-heap определяется как O(k + (n-k)log k) как упомянуто здесь ссылка Может ли оно быть приближено к O((n-k) log k)?

Так как O(N+Nlog(k))=O(Nlog(k)) выше аппроксимации, также верно?

Answer 1

Нет, вы не можете упростить это так. Это может быть показано с несколькими примерами значений для k , близких к n :

k = n

Теперь сложность определяется как: O (n + 0log n) = O (n) . Если бы вы пропустили первый член суммы, вы бы закончили с O (0) , что, очевидно, неправильно.

k = n - 1

Мы получаем: O ((n-1) + 1log (n-1)) = O (n + log (n)) = O (n ) . Без первого слагаемого вы получите O (log (n)) , что опять-таки неверно.