Действительно ли возможно вычислить, медиана списка чисел лучше, чем O (n регистрируют n)?

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

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

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

• Мы говорим о медианах? Итак, Gg на страницу о медианах в википедии.
• Страница поиска для алгоритма:

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

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

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

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

• А если вы ' Если интересно, прочтите о реальном гениальном алгоритме .

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

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

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

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

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

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

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

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