Средняя сложность времени нахождения элементов top-k

Question

Рассмотрите задачу поиска элементов top-k в наборе из N независимых и одинаково распределенных значений с плавающей запятой. При использовании очереди приоритетов/кучи, мы можем перебирать один раз по всем N элементов и поддерживать топ-K установить с помощью следующих операций:

• если элемент х «хуже», чем голова кучного в: отбрасывать х ⇒ сложности O (1)

• если элемент х «лучше», чем голова кучи в: удалить головку и вставить х ⇒ сложности O (Log к)

в худшем случае временная сложность этот подход, очевидно, O (N log k), но как насчет средней сложности времени? Благодаря н.о.р.-предположению, вероятность из O (1) операции возрастает с течением времени, и мы редко приходится выполнять дорогостоящую O (вход к), особенно к < < Н.

Это среднее время сложность документирована в любой цитируемой ссылке? Какова средняя временная сложность? Если у вас есть ссылка на ваш ответ, пожалуйста, включите его.

Answer 1

Рассмотрим i-й наибольший элемент и определенную перестановку. Он будет вставлен в кучу размера k, если она появится не более, чем k-1 из (i - 1) больших элементов в перестановке.

Вероятность того, что эта загрузка кучи будет равна 1, если i < = k, и k/i, если i> k.

Из этого вы можете вычислить математическое ожидание числа настроек кучи, используя линейность ожиданий. Сумма (i = 1 до k) 1 + sum (i = k + 1 до n) k/i = k + sum (i = k + 1 до n) k/i = k * (1 + H (n) - H (k)), где H (n) - n-го гармонического числа.

Это приблизительно k log (n) (для k < < n), и вы можете вычислить свою среднюю стоимость оттуда.