Метод уменьшения размера задачи. Метод «уменьшай и властвуй», страница 3

Такое среднее значение, называемое медианой (median), является одной из наиболее важных величин в математической статистике. Очевидно, мы можем найти k-ый по величине элемент, отсортировав весь список и выбрав k-ый по порядку элемент из отсортированного списка. Время работы такого алгоритма определяется эффективностью используемого алгоритма сортировки. При использовании хорошего алгоритма типа сортировки слиянием эффективность такого алгоритма порядковой статистики равна O(n*log2n).

Метод уменьшения размера задачи

Закрадывается подозрение, что сортировка всего списка – выполнение лишней работы, поскольку в задаче не требуется сортировать список, а надо только указать один-единственный элемент. К счастью, у нас имеется очень эффективный (в среднем) алгоритм для выполнения похожей задачи – разбиения элементов массива на два подмножества: одно из них содержит элементы, не превышающие некоторое опорное значение p, а второе – элементы, которые не меньше p. Такое разбиение является важной частью алгоритма быстрой сортировки. Как воспользоваться преимуществами такого разбиения?

Метод уменьшения размера задачи

Пусть s = k, где s – индекс опорного элемента, то опорный элемент p и есть решение задачи выбора. (Если элементы в списке нумеруются с 0, то, конечно, решение получается при s = k-1.) Если s>k, то k-ый наименьший элемент находится в левой части списка, а если s<k, то надо найти (k-s)-ый наименьший элемент из правой части списка. Итак, если мы не получаем решение задачи на данной итерации, то по крайней мере уменьшаем ее размер и получаем задачу, которая решается таким же методом, т.е. рекурсивно. На самом деле реализовать эту же идею можно и без рекурсии. При использовании нерекурсивной версии даже не надо изменять значение k – мы просто продолжаем выполнение вычислений, пока не получим s = k.

Метод уменьшения размера задачи

Пример. Найдем медиану списка из девяти элементов: 4, 1, 10, 9, 7, 12, 8, 2, 15. В этом случае k = [9/2] = 5, и наша задача состоит в поиске пятого по величине элемента массива. Как и ранее, мы предполагаем, что элементы в списке проиндексированы от 0 до 8. Мы можем воспользоваться той же версией разбиения, которой пользовались при рассмотрении алгоритма быстрой сортировки, т.е. выбирая в качестве опорного первый элемент и переставляя элементы в процессе двух противоположно направленных сканирований массива:

Метод уменьшения размера задачи

4 1 10 9 7 12 8 2 15 1 4 10 9 7 12 8 2 15 1 4 10 9 7 12 8 2 15 1 4 10 9 7 12 8 2 15 2 1 4 9 7 12 8 10 15 2 1 4 9 7 12 8 10 15 2 1 4 9 7 12 8 10 15 2 1 4 9 7 12 8 10 15 2 1 4 9 7 12 8 10 15

Метод уменьшения размера задачи

Поскольку s = 3 < k = 5, продолжаем работу с правой частью списка: 9 7 12 8 10 15 7 9 12 8 10 15 7 9 12 8 10 15 7 9 12 8 10 15 8 7 9 12 10 15 Поскольку s = 6 > k = 5, мы работаем с левой частью списка: 8 7 7 8 Теперь s = k = 5, так что можно остановиться: мы нашли медиану, равную 8 – которая больше 2, 1, 4 и 7, но меньше 9, 12, 10 и 15.

Метод уменьшения размера задачи

Насколько эффективен этот алгоритм? Следует ожидать, что в среднем он более эффективен, чем быстрая сортировка, т.к. работает только а одной частью исходного массива после разбиения, в то время как быстрая сортировка должна обработать обе части. Если считать, что разбиение всегда выполняется посредине оставшейся части массива, рекуррентное соотношение для количества сравнений будет иметь следующий вид: C(n) = C(n/2) + (n + 1), решение которого, согласно Основной теореме, равно O(n).