Почему алгоритм среднего значения медиан не может использовать размер блока 3?

Question

Я работаю на основе анализа детерминированных медианных результатов в предположении, что вход делится на 3 части, а не на 5, и вопрос в том, где он ломается?

алгоритм определения детерминированной медианы:

SELECT (i, n)

1. Разделите n элементов на группы по 5 человек. Найти медиану каждой группы из 5 элементов по порядку.

2. Рекурсивно ВЫБЕРИТЕ медиану х ⎣n / 5⎦ медианы группы должны быть осью.

3. Перегородка вокруг оси x. Пусть k = ранг (х)

4.Если i = k, то вернуть x

иначе, если я

затем рекурсивно ВЫБЕРИТЕ наименьший элемент в нижней части

еще рекурсивно ВЫБРАТЬ (i – k) -й наименьший элемент в верхней части

Я прошел анализ алгоритма и полагаю, что для шагов 1 и 3 потребуется O (n), где просто требуется постоянное время, чтобы найти медиану из 5 элементов, а для шага 2 - T (n / 5) .so по крайней мере 3/10 элементов имеют ≤ p, а по крайней мере 3/10 массива - ≥ p, поэтому Шаг 4 будет T (7n / 10) и получит повторение. T (n) ≤ cn + T (n / 5) + T (7n / 10), но когда я разделю элементы в группе из 3, скажем, 9 элементов, и я разделил их на группы так, чтобы:

{1,2,10} {4,11,14}, {15,20,22}

Я получил медианы 2,11,20 и р = 11.

в целом в группе из пяти, скажем, g = n / 5 групп и, по крайней мере, ⌈g / 2⌉ из них (те группы, медиана которых ≤ p), по крайней мере три из пяти элементов ≤ p. поэтому общее количество элементов ≤ p составляет не менее 3⌈g / 2⌉ ≥ 3n / 10. НО в группе из 3 мы можем получить все три элемента МЕНЬШЕ, чем р. и вот я думаю, что алгоритм сломается !!

Правильно ли я понял идею?

Answer 1

В группе из 3, как и в группах из 5, около половины групп будут иметь свой медианный элемент меньше, чем медиана медианы, поэтому в этих группах вы можете отбрасывать элементы меньше, чем их медиана. В вашем случае медиана (1,2,10) имеет значение меньше 11, поэтому вы можете сбросить 1 и 2.

Где я думаю, что для групп по 3 вещи распадаются, это затраты. 3 (этаж (этаж (n / 5) / 2 - 2), который примерно равен 3n / 10, становится 2 (этаж (этаж (n / 3) / 2 -2) или около того, что примерно равно n / 3. Это означает, что 7n / 10 становится 2n / 3. Этаж (n / 5) становится полом (n / 3), поэтому вместо 7cn / 10 + 2cn / 10 = 9cn / 10 вы получите только 2cn / 3 + cn / 3 = cn, и вместо T (n) <= cn у вас будет что-то, где вам придется внимательно присмотреться к терминам, не связанным с c, и вы можете в конечном итоге показать, что оно не является линейным в конце концов. </p>

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