Определение порядковых статистик

Порядковой статистикой порядка r для массива A называется значение элемента массива, который должен был бы стоять на r-м месте, если бы массив был сортирован по возрастанию.

Некоторые из порядковых статистик имеют специальные названия. Понятно, что статистика порядка 1 – это просто минимальный элемент массива, а порядка n – максимальный элемент. Статистика порядка n/2 называется медианой массива. Точнее говоря, при нечетном n медиана – это статистика порядка (n+1)/2 (средний по значению элемент массива), а при четном n медианой можно назвать любой из двух средних по значению элементов.

Порядковые статистики порядка n/4 и 3n/4 называются, соответственно, первой и третьей квартилями массива.

Понятно, что задача определения порядковых статистик родственна задаче сортировки массива. Радикальным способом определения сразу всех порядковых статистик является именно сортировка, после которой нужная статистика определяется непосредственно по индексу. Таким образом, задача определения всех порядковых статистик имеет оценку времени T(n) = O(n×log(n)). Однако в тех случаях, когда требуется определить лишь одну или несколько статистик, сортировка является избыточным решением. Для этой задачи существуют более быстрые алгоритмы, которые являются как бы «облегченными версиями» алгоритмов сортировки.

Отметим для начала, что задача определения первой и последней статистик (т.е. минимального и максимального значений) выполняется за один проход по массиву и, стало быть, имеет оценку эффективности T(n) = O(n). Если ставится задача определения небольшого фиксированного числа «крайних» статистик (например, «найти три минимальных значения»), то можно, немного усложнив программу, по-прежнему справиться за один проход.

Более общая постановка задачи «найти k наименьших (наибольших) значений» требует более регулярного подхода. Самое простое решение – выполнить k проходов алгоритма сортировки выбором (п. 3.2.2), после чего нужные элементы окажутся в начале таблицы. Оценка эффективности такого решения T(k, n) = O(kn).

Другой способ решения той же задачи – применить в неполном виде алгоритм HeapSort (подразд. 3.5). Следует сначала выполнить фазу построения пирамиды, что потребует времени T(n) = O(n). Затем надо выполнить k проходов второй фазы алгоритма. Напомним, что каждый такой проход заключается в перестановке первого (максимального) элемента пирамиды с последним, после чего максимальный элемент исключается из пирамиды, а новый первый элемент просеивается через пирамиду за время порядка O(log(n)). Таким образом, k наибольших элементов будет найдена за время T(k, n) = O(n + k×log(n)). Обычно это получается быстрее, чем с помощью простого выбора.

Описанные подходы плохо подходят для таких задач, как определение медианы и квартилей. Поскольку для медианы k = n/2, неполный HeapSort дает оценку T(n) = O(n×log(n)), т.е. работает ненамного быстрее, чем полная сортировка. Лучшим решением здесь является использование неполного алгоритма QuickSort (подразд. 3.4). Напомним, что в полном QuickSort после того, как массив разделен на две части, такое же разделение должно рекурсивно применяться к каждой из полученных частей. Для определения же, например, медианы массива интересна только одна из полученных частей, а именно та, которая включает в себя средний (по индексу) элемент массива. Только эта часть массива может включать в себя медианный элемент, поэтому только к ней следует применить следующую операцию разделения. Вместо рекурсивного разветвления имеем последовательное итеративное уточнение интервала, содержащего медиану. Можно ожидать, что этот алгоритм должен работать значительно быстрее обычного QuickSort. На самом деле оказывается, что неполный QuickSort обеспечивает в среднем линейное время отыскания медианы (или любой другой порядковой статистики с заданным номером k): T_ср(n) = O(n). К сожалению, оценка для худшего случая гораздо хуже: T_макс(n) = O(n²). Однако в [3] описана достаточно заковыристая модификация неполного QuickSort, которая обеспечивает линейную оценку времени отыскания порядковой статистики даже в худшем случае. Это достигается применением довольно сложной процедуры выбора разделяющего элемента.

Для большинства приложений можно довериться хорошей средней оценке обычного неполного QuickSort и не усложнять себе жизнь дополнительными ухищрениями. Исключение составляют те редкие случаи, когда даже маловероятная задержка выполнения абсолютно недопустима, и потому надо применять пусть сложную, но гарантированно быструю процедуру.