Я знаю, что можно вычислить среднее из списка чисел в O (n). Но как насчет медианы? Есть ли лучший алгоритм, чем sort (O (n log n)) и средний средний элемент (или средний из двух средних элементов, если четное количество элементов в списке)?
Можно ли вычислить медиану списка чисел лучше, чем O (n log n)?
Ответ 1
Ответ 2
Что вы говорите, это алгоритм выбора, где k = n/2. Существует метод, основанный на той же функции разбиения, которая используется в quicksort, которая работает. Это не удивительно, quickselect. Хотя он может, как и quicksort, иметь наихудший случай O (n 2), это можно свести к линейному времени, используя proper выбор поворота.
Ответ 3
Частично неуместно, но: быстрый совет о том, как быстро найти ответы на общие основные вопросы, подобные этому в Интернете.
- Мы говорим о медианах? Итак, Gg to страница о медианах в википедии
- Страница поиска для алгоритма:
Эффективное вычисление медианы образца
Несмотря на то, что при сортировке n элементов выполняются общие операции O (n log n), используя алгоритм "divide and conquer", медианная из n элементов может быть вычислена только с помощью операций O (n) (на самом деле вы всегда можете найдите k-й элемент списка значений с помощью этого метода, это называется проблемой выбора ).
- Следуйте ссылке на проблему выбора для описания алгоритма. Прочтите ввод:
... Существуют алгоритмы выбора временного времени наихудшего случая....
- И если вам интересно узнать о фактическом гениальном алгоритме.
Ответ 4
Если числа являются дискретными (например, целыми числами) и существует управляемое количество различных значений, вы можете использовать "сортировку ведра", которая является O (N), а затем перебирать ведра, чтобы выяснить, какой ведро содержит медиану, Полный расчет O (N) во времени и O (B) в пространстве.
Ответ 5
Просто для удовольствия (и кто знает, может быть, быстрее) есть еще один рандомизированный медианный алгоритм, который технически объясняется в книгах Мицценмахера и Уппалла. В принципе, вы выбираете полиномиально меньший поднабор списка и (с некоторыми причудливыми книгами), чтобы он, вероятно, содержал реальную медианную форму, а затем использовал ее для поиска реальной медианы. Книга находится в книгах Google, а здесь ссылка. Примечание. Я смог прочитать страницы algorthm, поэтому, предполагая, что книги Google показывают одинаковые страницы для всех, вы также можете их прочитать.
Это рандомизированный алгоритм s.t. если он найдет ответ, он на 100% уверен, что это правильный ответ (это называется стиль Лас-Вегаса). Случайность возникает из-за времени выполнения - иногда (с вероятностью 1/(sqrt (n)), я думаю), она НЕИСПРАВНОСТИ, чтобы найти медиану и должна быть повторно запущена.
Асимптотически, это точно линейно, когда вы принимаете шанс на неудачу, то есть это бит, который меньше, чем линейный, именно так, когда вы учитываете количество раз, которое вам может понадобиться перезапустите его, он станет линейным.
Примечание. Я не говорю, что это лучше или хуже. Я, конечно же, не провел реального сравнения времени выполнения этих алгоритмов! Я просто представляю дополнительный алгоритм с линейным временем выполнения, но работает по-другому.
Ответ 6
Эта ссылка появилась недавно при вычислении медианы: http://matpalm.com/median/question.html.
В общем, я думаю, что вы не можете выйти за пределы O (n log n), но у меня нет никаких доказательств на этом:). Независимо от того, насколько вы делаете его параллельным, объединение результатов в одно значение занимает не менее log n уровней выполнения.
Ответ 7
Попробуйте рандомизированный алгоритм, размер выборки (например, 2000) не зависит от размера данных n, тем не менее, сможет получить достаточно высокую (99%) точность. Если вам нужна более высокая точность, просто увеличьте размер выборки. Использование границы Чернова может доказать вероятность при определенном размере выборки. Я написал код JavaScript для реализации алгоритма, не стесняйтесь его брать. http://www.sfu.ca/~wpa10