Можно ли рассчитать медиану списка чисел лучше, чем O (n log n)? - PullRequest
Новая
       9

Можно ли рассчитать медиану списка чисел лучше, чем O (n log n)?

11 голосов
/ 21 августа 2009

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

Ответы [ 7 ]

16 голосов
/ 21 августа 2009
13 голосов
/ 21 августа 2009

То, о чем вы говорите, это алгоритм выбора , где k = n/2. Существует метод, основанный на той же функции разделения, которая используется в быстрой сортировке, которая работает. Неудивительно, что он называется quickselect . Хотя он может, как и быстрая сортировка, иметь наихудший случай O (n 2 ), его можно уменьшить до линейного времени, используя правильный выбор поворота .

6 голосов
/ 21 августа 2009

Частично не имеет значения, но: быстрый совет о том, как быстро найти ответы на распространенные базовые вопросы, подобные этому, в Интернете.

Эффективное вычисление медианы выборки

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

  • Перейдите по ссылке на задачу выбора для описания алгоритма. Прочитайте вступление:

... Существуют алгоритмы линейного выбора времени в худшем случае. ...

4 голосов
/ 21 августа 2009

Если числа дискретные (например, целые числа) и имеется управляемое количество различных значений, вы можете использовать «сортировку сегментов», которая равна O (N), затем выполнить итерацию по сегментам, чтобы выяснить, в каком сегменте содержится медиана , Полный расчет: O (N) во времени и O (B) в пространстве.

2 голосов
/ 21 августа 2009

Просто для забавы (и кто знает, это может быть быстрее) есть еще один рандомизированный медианный алгоритм, технически объясненный в книге Митценмахера и Апфолла. По сути, вы выбираете подмножество списка с полиномиально меньшими размерами (и с некоторыми причудливыми книгами) так, чтобы оно, вероятно, содержало реальную медиану, а затем использовали его для поиска настоящей медианы. Книга на Google Books, и вот ссылка . Примечание. Мне удалось прочитать страницы алгоритма, так что, предположив, что книги Google открывают одинаковые страницы для всех, вы тоже можете их прочитать.

Это рандомизированный алгоритм с.т. если он находит ответ, то он на 100% уверен, что это правильный ответ (это называется стилем Лас-Вегас). Случайность возникает из среды выполнения - иногда (с вероятностью 1 / (sqrt (n)), я думаю) она НЕ СМОЖЕТ найти медиану и должна быть повторно запущена.

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

Примечание: я не говорю, что это лучше или хуже - я, конечно, не проводил сравнения между этими алгоритмами в реальном времени! Я просто представляю дополнительный алгоритм, который имеет линейное время выполнения, но работает существенно другим способом.

1 голос
/ 09 ноября 2014

Попробуйте рандомизированный алгоритм, размер выборки (например, 2000) не зависит от размера данных n, при этом можно получить достаточно высокую (99%) точность. Если вам нужна более высокая точность, просто увеличьте размер выборки. Использование границы Черноффа может доказать вероятность при определенном размере выборки. Я написал код JavaScript для реализации алгоритма, не стесняйтесь его использовать. http://www.sfu.ca/~wpa10

1 голос
/ 21 августа 2009

Эта ссылка недавно появилась при расчете медианы: http://matpalm.com/median/question.html.

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

...