о выборе алгоритма

Question

Я читал о selection algorithm, и у меня есть вопрос, может быть, это выглядит глупо! но почему мы рассматриваем массив как группы из 5 элементов? можем ли мы рассмотреть его с 7 или 3 элементами? Спасибо также есть ли какая-либо ссылка, чтобы помочь мне лучше понять эту цель?

также это мое доказательство, когда мы рассматриваем массив с 3 элементами, и это все еще порядок n, почему? Это правильно?

T(n)<=T(n/3)+T(n/3)+theta(n) 
claim: T(n)<=cn 
proof: For all k<=n : T(n)<=ck 
    T(n)<=(nc/3)+(nc/3)+theta(n) 
    T(n)<= (2nc/3)+theta(n) 
    T(n)<=cn-(cn/3-theta(n)) and for c>=3 theta(n) this algorithm with this condition will have an order of n,too !!!! 

Answer 1

Я думаю, что вы допустили ошибку для T (n). Это должно быть T (n) = T (n/3) + T (2n/3) + O (n).

T (n/3) предназначен для нахождения стержня (медиана медиан). Только половина всех n/3 групп имеет медиану меньше, чем ось. Эти группы имеют 2 элемента, меньшие, чем опорный стержень. Предоставление 2 * (1/2 * n/3) == n/3 элементов, меньших точки поворота. Таким образом, только 33% должны быть меньше, чем опорный стержень (и 33% должны быть больше, чем опорный стержень). Итак, в худшем случае у вас все еще есть 66% для следующей итерации, T (2n/3).

Я не могу хорошо прочитать ваши доказательства, но теперь это невозможно доказать. Правильно?

Answer 2

Немного по поиску в Интернете и я нашел this. Существует очень небольшой раздел о том, почему 5, но на самом деле он не отвечает конкретно на ваш вопрос, кроме как сказать, что это наименьшее возможное нечетное число, которое можно использовать (должно быть нечетным, чтобы дать медианную). Существует некоторое математическое доказательство того, что его не может быть 3 (но я сам этого не понимаю). Я думаю, что это в основном говорит, что это может любое нечетное число, 5 или больше, но чем меньше, тем лучше, я думаю, потому что быстрее будет найти медиану в меньшей группе?