Точное количество сравнений для вычисления медианы

Том III книги Кнута « Искусство компьютерного программирования» (глава 5, стих 3.2) включает в себя следующую таблицу, в которой перечислено точное минимальное количество сравнений, необходимых для выбора наименьшего элемента $t$ из несортированного набора размера $n$ для всех $1\le t \le n\le 10$ . Эта таблица вместе с известными выражениями в замкнутой форме $V_1(n) = n-1$ и $V_2(n) = n - 2 + \lceil n/2 \rceil$ , представляетбольшуючасть современного уровня техникис 1976 года.

Таблица от Кнута III: 5.3.2

Были ли рассчитаны более точные значения $V_t(n)$ за последние 36 лет? Меня особенно интересуют точные значения $M(n) = V_{\lceil n/2 \rceil}(n)$ , минимального количества сравнений, необходимых для вычисления медианы.

Как указывает @ MarkusBläser, таблица Кнута, похоже, уже включает более поздние результаты Билла Гасарча, Уэйна Келли и Билла Пью ( Нахождение i-го наибольшего из n для малых i, n . SIGACT News 27 (2): 88-96, 1996 .)

ds.algorithms reference-request co.combinatorics sorting selection Jeffε
источник

Я думаю, что самой известной статьей на эту тему является работа Пратта и Яо (1976), которой приписывают то, что они одними из первых нашли некую (состязательную) технику для доказательства нижних границ этой проблемы. Если бы я нашел последние статьи по этому вопросу, я бы следовал цитатам, сделанным в этой статье . Самая свежая статья - «Дор и Цвик», но есть также опрос Патерсона, проведенный в 1996 году (хотя я не смотрел, касается ли он точных результатов или нет).

Джереми

Nitpicking: В последнем предложении вопроса вы, вероятно, имели в виду потолок, а не пол.

Цуёси Ито

Джефф, любопытно, почему вы заинтересованы в точном ответе.

Чандра Чекури,

V_{i} (n)

$V_i(n)$

@ChandraChekuri: я играю с вариантами алгоритма линейного выбора времени Блюма-Флойда-Пратта-Ривеста-Тарьяна , как потенциальную проблему домашней задачи алгоритмов. Если мы используем алгоритм сравнения минимума, чтобы найти медиану в каждом блоке, то какой размер блока дает нам лучшую константу в большом-Oh? 9 лучше чем 7 лучше чем 5; а как насчет 11?

Джефф

Интересно, может ли эта информация быть полезной для вас? К сожалению, он не предоставляет никакой дополнительной информации к вопросу этого поста, но скорее отвечает на ваш комментарий о том, для чего это было сделано (анализ вариантов QuickSelect).

$v(n,t)$ $v_t(n)$

v_{T} (N) знак равно N + мин (T, N - T) + много,

$v_t(n)=n+\min(t,n-t)+\text{l.o.t.}.$

Этот результат нередко используется и, в частности, является основой для алгоритмов «Адаптивная выборка для быстрого выбора» Мартинеса, Панарио и Виолы . Отправной точкой статьи является QuickSelect медиана-три, а затем спросить: уместно ли систематически выбирать медиану, когда искомый элемент имеет относительный ранг, намного меньший, чем n / 2, или намного выше, чем n / 2? ?

$k$ $n$ $m$ $m/2$ $\alpha m$ $\alpha = k/n$ $m$

Жереми
источник

Точное количество сравнений для вычисления медианы

Ответы: