В алгоритме медианных медианов нам нужно разделить массив на куски размера 5. Мне интересно, как изобретатели алгоритмов придумали магическое число «5», а не, может быть, 7 или 9 или что-то еще?Алгоритм медианы медианов: зачем делить массив на блоки размером 5
Я думаю, что если вы будете проверять «Доказательство O (N) Время работы в режиме» раздел вики страницы для medians-of-medians algorithm:
Медиана-вычисления рекурсивный вызов не превышает наихудший линейное поведение, потому что список медиан составляет 20% от размера списка, а другой рекурсивный вызов рекурсивен на не более 70% от списка, что делает время работы
о (п) термин сп для работы с разбиением (мы посетили каждый элемент con чтобы сформировать их в n/5 групп и взять каждую медиану в O (1) раз). Исходя из этого, с помощью индукции, можно легко показать, что
Это должно помочь вам понять, почему.
Число должно быть больше 3 (и нечетное число, очевидно) для алгоритма. 5 - наименьшее нечетное число, большее 3. Таким образом, было выбрано 5.
Это не должно быть больше tan 3 (и нечетно), см. Мой ответ ниже. –
Да, но это другой алгоритм. Это лишь небольшая вариация алгоритма, о котором спрашивал OP, но это все еще другой алгоритм. ОП спросил: «Почему в этом конкретном алгоритме нам нужно использовать блоки из 5», а не «есть вариант по этому алгоритму, где мы могли бы использовать более мелкие блоки». Они пытались понять, как что-то было рассчитано, а не пытаться найти, есть ли что-то другое, что может сделать это лучше. – rabensky
Вы также можете использовать блоки размером 3 или 4, как показано в документе Select with groups of 3 or 4 К. Чен и А. Думитреску (2015). Идея состоит в том, чтобы дважды использовать алгоритм «медианы медианов» и разделять только после этого. Это снижает качество поворота, но быстрее.
Таким образом, вместо:
T(n) <= T(n/3) + T(2n/3) + O(n)
T(n) = O(nlogn)
один получает:
T(n) <= T(n/9) + T(7n/9) + O(n)
T(n) = Theta(n)
Это доказывает O (N) Время работы с использованием 20%, это не опровергающей O (п) время работы какого-либо другого процента (если какой-то другой процент был также O (n), это не оправдывает выбор на 20% выше другого). – Dukeling