Порядковая статистика: k-й элемент без полной сортировки

Если ты знаешь, что такое k-я порядковая статистика и медиана, понимаешь, почему полная сортировка ради одного элемента - перебор, и почему минимум ищется за Θ(n), листай до «Теперь сам».

Как думаешь, обязательно ли сортировать весь массив ради одного элемента

Тебя просят: «найди пятый по величине результат забега». Первое, что приходит в голову, - отсортировать все результаты и взять пятый. Это работает, но задумайся: ты упорядочил ТЫСЯЧУ бегунов, чтобы узнать одного. Не слишком ли много? Ведь минимум - первую порядковую статистику - ты находишь без всякой сортировки, одним проходом с запоминанием наименьшего. Максимум - тоже. Раз для k = 1 и k = n сортировка не нужна, возникает подозрение, что она не нужна и для остальных k. Прежде чем искать быстрый способ, надо чётко назвать, ЧТО именно мы ищем, - иначе легко решить не ту задачу.

На что это похоже

Соревнование по прыжкам, и тебе нужен только бронзовый призёр - третье место. Ты не обязан выстраивать всех сорока участников по росту результата от первого до последнего. Достаточно как-то отделить трёх лучших от остальных и среди этих трёх найти слабейшего. Работы явно меньше, чем полное ранжирование всех сорока. Задача выбора ровно про это: получить элемент НУЖНОГО ранга, не тратя силы на упорядочивание всех прочих, чей порядок тебе безразличен. Порядок «всех остальных» - это работа, за которую ты платишь зря.

Механизм: определения и наивное решение

Пусть массив a из n элементов. Отсортируем его мысленно по возрастанию. Тогда:

• k-я порядковая статистика - элемент на позиции k в этом отсортированном порядке (нумеруем с 1): k = 1 - минимум, k = n - максимум.
• Медиана - «средний» элемент: при нечётном n это ((n+1)/2)-я статистика; при чётном обычно берут нижнюю медиану, (n/2)-ю. Медиана делит данные пополам: половина меньше, половина больше. Она устойчивее среднего к выбросам - один гигантский элемент сдвинет среднее, но не медиану.

Наивное решение задачи выбора:

отсортировать a            # Θ(n·log n)
вернуть a[k-1]             # порядковая статистика с номером k (индексация с 0)

Верно и просто, но цена - Θ(n·log n). При этом крайние случаи мы умеем за линию:

минимум: один проход, помним наименьшее           # Θ(n)
максимум: один проход, помним наибольшее          # Θ(n)

Правило

k-я порядковая статистика - элемент на позиции k в отсортированном порядке (k = 1 - минимум, k = n - максимум, ≈ n/2 - медиана). Задача ВЫБОРА - найти её, не сортируя весь массив. Наивно решается полной сортировкой за Θ(n·log n) и взятием a[k−1], но это избыточно: чтобы узнать один элемент, упорядочивается весь массив. Минимум и максимум находятся за Θ(n) одним проходом. Медиана как «серединный» элемент устойчивее среднего к выбросам, поэтому её ищут особенно часто.

Разбор: почему медиана, а не среднее арифметическое

Медиана и среднее отвечают на разные вопросы, и путать их дорого. Среднее - это сумма, делённая на количество; один выброс тянет его за собой. Возьми зарплаты [30, 32, 35, 40, 1000] (в тысячах): среднее - 227, хотя четверо из пяти получают около 35. Медиана - третий по порядку элемент, 35, - честно показывает «типичного» человека, потому что зависит от ПОЗИЦИИ, а не от величины крайних значений. Поэтому медиану берут там, где есть выбросы: доходы, времена отклика сервера (медианная задержка честнее средней), цены на жильё. А чтобы найти медиану, нужна именно порядковая статистика с номером n/2 - вот почему задача выбора практически важна, а не только академична.

Разбор: почему полная сортировка - это перебор для одной статистики

Сортировка упорядочивает ВСЕ n элементов - то есть находит СРАЗУ все n порядковых статистик. Но нам нужна одна. Мы платим Θ(n·log n) за информацию, которая на 99% не нужна: порядок элементов, стоящих не на позиции k, нам безразличен. Сравни с крайними случаями: минимум - это первая статистика, и мы находим её за Θ(n), не узнав ничего о порядке остальных. Значит принципиально возможно узнать элемент нужного ранга, НЕ упорядочивая соседей. Разрыв между Θ(n) (что мы платим за min/max) и Θ(n·log n) (что берёт сортировка за произвольный k) - это и есть пространство для лучшего алгоритма. Следующий урок покажет, как разбиение (то самое, из быстрой сортировки) закрывает этот разрыв: спускаясь только в ОДНУ половину, выбор находит любую статистику за Θ(n) в среднем.

Что ломается без этого

Первая путаница - индексация: k-я статистика (нумерация с 1) - это a[k−1] в массиве (нумерация с 0). Промах на один тут - самая частая ошибка. Вторая - считать, что медиана всегда одна: при чётном n «серединных» элемента два, и нужно заранее договориться, берём нижнюю (n/2-ю) или верхнюю - иначе разные реализации дадут разные ответы. Третья - хвататься за полную сортировку там, где нужен один элемент: на больших данных это лишний множитель log n, а иногда и лишняя Θ(n) память под сортировку копии. Четвёртая - путать медиану со средним и получать «типичное значение», изуродованное выбросами.

Зачем это в работе

Порядковые статистики - повседневный инструмент. Медиана - честная «типичная» величина при выбросах (зарплаты, цены, задержки). Перцентили (95-й, 99-й) - это порядковые статистики с номерами 0.95n, 0.99n, и мониторинг задержек сервиса живёт именно на них: «99-й перцентиль ответа - 200 мс» значит, что 99% запросов быстрее. Топ-k (k крупнейших) сводится к поиску (n−k)-й статистики как порога. Везде, где нужен элемент определённого РАНГА, а не полный порядок, задача выбора экономит множитель log n против сортировки - а на потоках данных, где сортировать всё невозможно, она вообще единственный путь. Осознать, что «мне нужен один по рангу» - это НЕ «мне нужно всё отсортировать», - первый шаг к быстрому решению.

Теперь сам

В массиве [8, 3, 5, 1, 9, 2, 7] (n = 7) назови 1-ю, 4-ю и 7-ю порядковые статистики. Какая из них медиана и почему полная сортировка ради, скажем, только 4-й - перебор?