Постройте алгоритм, который по данному массиву $%A[1…n]$% выводит его минимальные $%\sqrt{n}$% элементов в порядке возрастания (другими словами, выводит $%A'[1 \ldots \sqrt{n}]$% за время $%O(n)$%.

задан 29 Ноя '15 2:30

10|600 символов нужно символов осталось
3

Создадим два массива длины $%\sqrt{n}$%. Сначала заполним первыми $%\sqrt{n}$% элементами исходного массива первый. Затем будем идти дальше по исходному и заполнять второй. Когда он заполнится, создадим массив из $%2\sqrt{n}$% элементов, куда положим первый и второй массивы подряд.

Далее воспользуемся неполным алгоритмом быстрой сортировки: возьмем любые 3 элемента, посчитаем среднее арифметическое, это будет число $%x$%, близкое к медиане. Будем идти от первого элемента и от последнего, и каждый раз, когда левый элемент больше $%x$%, а правый меньше, меняем их местами. Указатели будут встречаться с очень большой вероятностью близко к середине. Если они встретились дальше середины, то повторяем тоже самое на массиве от начала до места встречи, если до середины, то тоже самое на отрезке от места встречи до конца. И так делаем, пока они не встретятся на середине этого большого массива. Тогда в левой части мы получим минимальные $%\sqrt{n}$% элементы объединенного массива. Перекидываем их в первый массив, а второй очищаем. Продолжаем двигаться по исходному массиву и добавлять элементы во второй, пока он не заполнится.

Итого на каждые $%\sqrt{n}$% элементов исходного массива не более $%2\sqrt{n}$% действий(когда мы объединяем массив мы каждый раз запускаем итерацию быстрой сортировки на массиве, который с очень большой вероятностью в $%\approx 2$% раза меньше предыдущего), следовательно сложность алгоритма $%\in O(n)$%.

В конце не забудем отсортировать первый массив за $%\sqrt{n}\log \sqrt{n}=0.5\sqrt{n}\log n$%, что $%\in O(n)$%, что несложно доказать.\

P.S. если не жалеть памяти, то можно сразу делать итерации быстрой сортировки в большом массиве. Тогда доп. массивы не нужны.

ссылка

отвечен 29 Ноя '15 5:32

изменен 29 Ноя '15 6:18

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×229
×142
×130
×84
×66

задан
29 Ноя '15 2:30

показан
960 раз

обновлен
29 Ноя '15 6:18

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru