Есть ли алгоритм для нахождения log (n) порядка статистики за линейное время - PullRequest
Новая
       57

Есть ли алгоритм для нахождения log (n) порядка статистики за линейное время

0 голосов
/ 19 декабря 2018

Могу ли я построить алгоритм FindStats (A, k)

, который получает входной массив A размера n и целое число k, такое что 2 ^ k <= n (что означает, что k в худшем случаеlog (n)) и выводит статистику заказов A 1,2,4,8, ..., 2 ^ k.все это за линейное время! </p>

Что я пробовал до сих пор:

Я знаю, что есть алгоритм QuickSelect (A, k) (детерминированный алгоритм), который возвращает статистику k-го порядка влинейное время, но в моем случае тривиальное решение, которое состоит в том, чтобы просмотреть всю статистику порядка 1,2,4,8 ..., 2 ^ k и вернуть результат, приведет к O (nlogn).

Могу ли я улучшить это?Можно ли вообще этого достичь?

1 Ответ

0 голосов
/ 20 декабря 2018

Я думаю, что в ответе Джима Мишеля использовалась похожая логика.Я не уверен, почему этот ответ был удален.

Если мы признаем, что существует какой-либо алгоритм выбора, который может гарантировать одну статистику k порядка за время O(n), то нахождение 1st, 2nd, 4th, 8th..., 2^kthтакже достижимо в O(n) раз.Это происходит из-за простой алгебры: 

let a = 2^k
then the sequence,
  a + 1/2*a + 1/4*a + 1/8*a + 1/16*a ...
converges and can never exceed 2*a

Это означает, что если после (или во время) каждого выбора мы разделим список на раздел, равный половине его размера, и сделаем так, чтобы вход для следующего выбора, общий входПереходим к алгоритму выбора, никогда не превысившему O(n).Наш расчет времени будет выглядеть следующим образом: 

find 2^kth:       n
find 1/2 * 2^kth: 2^k
find 1/4 * 2^kth: 2^(k-1)
find 1/8 * 2^kth: 2^(k-2)
...

The sum on the right cannot exceed
n + 2^(k + 1)
=> O(n + 2^(log2(n) + 1))
=> O(n)

(If it takes an extra traversal to
 partition the list after each selection,
 the summation could add another n,
 not affecting the general complexity.)

Еще одна идея, которая меня заинтересовала, заключается в том, можем ли мы каким-то образом использовать метод кучи, чтобы гарантировать, что все кузены меньше, чем кузены на следующем уровне.Выполнение этого достаточно эффективно может также гарантировать решение O (n) с использованием поиска в ширину для прохождения каждого уровня этой специальной кучи.

...