найти приблизительную медиану в несортированном списке

Я хочу найти приблизительную медиану в несортированном списке, я знаю два алгоритма

алгоритм 1 - быстрый выбор

алгоритм 2- Медиана медиан

Я не могу использовать quickselect в своем проекте, потому что в худшем случае он занимает O (n ^ 2). Я слышал о медиане медиан, но мои коллеги предполагают, что для этого требуется O (n) с некоторым постоянным коэффициентом. поэтому его временная сложность равна Cn, а постоянный коэффициент велик по сравнению с quickselect. Я хочу знать, каков постоянный коэффициент, связанный с Медианой медиан? и почему Медиана медиан не использует псевдомедиану из 9 элементов?
или есть ли их какой-либо другой алгоритм для поиска приблизительной медианы за линейное время O (n)?


algorithm median-of-medians quickselect
person asd    schedule 18.02.2014    source источник
comment
см. stackoverflow.com/questions/9489061/   -  person Aseem Goyal    schedule 18.02.2014
comment
возможный дубликат Поиск медианы несортированного массива   -  person Jim Mischel    schedule 18.02.2014
comment
Вы задаете 3 довольно разных вопроса - вероятно, было бы лучше разделить их на 3 разных вопроса, потому что задавать несколько вопросов в вопросе на самом деле не работает в Формат Stack Overflow (на последний уже есть ответ, так что это очевидный выбор, который следует оставить в этом вопросе). Википедия отвечает на ваш второй вопрос, если вы его понимаете. Первые два вопроса, вероятно, лучше подходят для информатики, но оба могут потребовать от вас немного работы, чтобы попытаться понять это. из себя.   -  person Bernhard Barker    schedule 18.02.2014

Ответы (1)


arrow_upward
0
arrow_downward

Хотя я бы не стал отказываться от quickselect, так как его производительность в худшем случае маловероятна при правильно выбранных точках поворота ...

Возможно, introselect:

Introselect (сокращение от «интроспективный выбор») - это алгоритм выбора, который представляет собой гибрид быстрого выбора и медианы медиан, который имеет высокую среднюю производительность и оптимальную производительность в худшем случае.

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

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

Оба подхода ограничивают глубину рекурсии до k ⌈log n⌉ = O (log n), а общее время выполнения - до O (n).

person Bernhard Barker    schedule 18.02.2014