Алгоритм поиска k-й порядковой статистики.

В прошлом уроке вы узнали, какой алгоритм применяется в Трешландии для определения нарушителей. Этот алгоритм начали применять очень давно. Тогда жителей в стране было совсем немного. На таком объёме данных программа отрабатывала за считанные секунды.
С тех пор количество жителей постоянно росло. А после очередной волны миграции из Котостана и Песикостана на юг Трешландии, количество её жителей сильно увеличилось. На таком объёме данных алгоритм стал работать очень медленно.
Пришло время решить вторую задачу, которую поручил король ребятам, — модифицировать существующий алгоритм.
Тимофей: Помните, я рассказывал вам про стратегию «разделяй и властвуй»?
Алла: Да, забудешь про такое!
Рита: А к чему это ты?
Тимофей: Есть алгоритмы сортировки, которые работают быстрее чем сортировка выбором. Про один из них я расскажу. Но перед тем, как перейти к его изучению, вам было бы полезно послушать про алгоритм поиска k-й порядковой статистики.
Алла: А что это такое?
Тимофей: k-й порядковой статистикой называется k-й по величине элемент массива.
Рита: А, то есть медиана — частный случай такой статистики, да?
Тимофей: Да, верно. Ведь медиана — такое число, которое делит массив пополам: в одной половине элементы не большие медианы, а в другой — не меньшие.
Гоша: Так, если в массиве нечётное количество чисел, то понятно, как найти медиану. Отсортировать и взять средний элемент. А что, если чисел чётное количество?
Тимофей: В этом случае в качестве медианы обычно берут полусумму двух соседних средних значений. Но при определении статистики нужно использовать значение определённого элемента, а не полусумму двух.
Обратите внимание, что медиана — не то же самое, что среднее значение. Например, для массива [1,1,1,1,1,10][1, 1, 1, 1, 1, 10] медиана равна 1, а среднее значение — 2.5.
Медиана — не единственный частный случай k-й порядковой статистики.
В случае, если массив из nn элементов сортируется по возрастанию, минимальный элемент массива — 1-я порядковая статистика, максимальный элемент будет иметь порядковую статистику nn.
Многие удивляются, когда узнают, какая вычислительная сложность у алгоритма поиска k-й порядковой статистики.
Гоша: (перебивает) А что тут думать, отсортировал массив встроенной сортировкой и берёшь какой k-й от начала элемент!
Тимофей: Ну и какая сложность алгоритма?
Гоша: Ой, извини, что перебил! Что ты там рассказывал?
Как думаете, за сколько можно найти k-й по порядку элемент в массиве?
Минимум в массиве (случай, когда k=1k = 1) можно найти за O(n)O(n).
При k=2k = 2 задачу тоже можно решить за один проход по массиву.
Всё просто: нужно хранить значения двух элементов — минимального и второго по величине. При обработке каждого следующего элемента возможны три случая:
  1. Элемент не больше минимального. Тогда он становится минимальным, а предыдущее значение минимума записывается во второй элемент.
  2. Элемент больше минимального, но не больше второго элемента. Тогда меняется значение только второго элемента.
  3. Элемент больше второго элемента. Здесь ничего не меняется.
На каждой итерации требуется не более двух сравнений.
Кажется, при k=3k = 3 или k=4k = 4 задача решается аналогично. Да и для произвольного kk тоже.
Как вы думаете, есть ли у этой идеи какие-то недостатки? (можно выбрать более одного варианта ответа)
2 из 3 правильно и 1 неправильно
Можно модифицировать алгоритм при помощи бинарного поиска. Это ускорит его работу.
Также можно воспользоваться предложением Гоши и отсортировать массив, взяв затем элемент на позиции kk.
Но есть решение лучше.
Воспользуемся алгоритмом, который основан на стратегии «разделяй и властвуй»:
image image image image
На практике этот алгоритм работает за линейное время. Почему так, вы узнаете чуть позже.