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

Question

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

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

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

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

Answer 2

Я думаю, что вы допустили ошибку для 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).

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