Сложность в среднем. Эффективность быстрой сортировки на практике

Гоша: Тимофей! Я всё-таки не до конца понял. Ты сказал, что алгоритм быстрой сортировки в худшем случае работает за $O(n^2)$. Потом привёл пример, когда ему требуется $O(n \log n)$ времени и уточнил, что на практике алгоритм работает с такой сложностью. Разве можно сделать этот вывод, рассмотрев только один случай? К тому же в этом примере ведущий элемент на каждом шаге удачно разделяет массив на две примерно равные части.

Тимофей: Одного примера недостаточно, чтобы понять, почему алгоритм обычно работает быстрее своей худшей оценки. Чтобы посчитать сложность в среднем, нужно учесть всевозможные варианты входных данных и усреднить по ним время работы алгоритма.

Допустим, нужно найти определённый элемент в массиве. Сложность этой операции в худшем случае $O(n)$. Худший случай — когда искомый элемент находится в конце массива или вовсе отсутствует.

Но, возможно, искомый элемент расположен в самом начале массива. Тогда мы найдём его всего за одну операцию вне зависимости от размера массива.

Эти случаи маловероятны. Нам интересен ожидаемый результат, когда нужный элемент находится в произвольном месте массива. В среднем понадобится $\displaystyle \frac{n}{2}$ операций. Значит, сложность этого алгоритма в среднем — $O \displaystyle \left (\frac{n}{2}\right)$, то есть $O(n)$.

Гоша: Тоже мне, удивил! Такая же оценка и в худшем случае.

Тимофей: Для некоторых алгоритмов сложность в худшем случае и сложность в среднем не совпадают.

Гоша: Судя по всему, быстрая сортировка — один из таких алгоритмов, верно?

Тимофей: Да. И алгоритм поиска k-й порядковой статистики тоже.

Напомним, что в рекурсивном алгоритме поиска k-й порядковой статистики выбирают опорный элемент и разбивают массив на три части, в которых располагают: элементы, меньшие $(S_l)$, равные $(S_v)$ и большие опорного$(S_r)$.

Худший случай наступает, если ведущим элементом выбран наименьший или наибольший элемент массива. То есть оказывается, что $|S_l| = 0$ либо $|S_r| = 0$. Тогда, как мы показали в уроке, посвященному этому алгоритму, сложность получится:

Но вероятность $p$ такого события очень маленькая:

Гоша: Так, полегче! Я на четверть гуманитарий, между прочим. Объясни, пожалуйста, почему вероятность такая.

Тимофей: Помнишь, как найти вероятность события?

Гоша: Да, нужно количество благоприятных исходов поделить на количество возможных исходов.

Случай $i = n$ соответствует началу алгоритма, когда мы рассматриваем все $n$ элементов.

Событие — элемент расположен на первой или последней позиции в массиве.

Вероятность события, что элемент окажется на первой или последней позиции в массиве равна $\displaystyle\frac{2}{n}$.

Тогда на следующем шаге длина массива уменьшится всего на 1 и станет равна $n - 1$.

Вероятность события, что элемент окажется на первой или последней позиции в массиве станет $\displaystyle\frac{2}{(n - 1)}$. И так далее. На каждом шаге длина массива уменьшается на один, а благоприятных исхода остаётся два. На последнем шаге, когда массив будет состоять всего из двух элементов, вероятность станет равна 1. Ведь выбранный элемент точно окажется либо на первой, либо на последней позиции в массиве.

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

$P(A\cdot B) = P(A) \cdot P(B)$.

Вероятность произведения независимых событий $A$ и $B$ равна произведению их вероятностей.

Гоша: А что значит, что события независимые?

Тимофей: События $A$ и $B$ называются независимыми, если появление одного из них не меняет вероятности появления другого. В нашем случае тот факт, что на каком-то шаге выбранный элемент оказался на первой или на последней позиции никак не влияет на вероятность такого события на следующем шаге.

То есть для вычисления общей вероятности нужно перемножить вероятности на каждом шаге. Именно это и сказано в формуле:

$p = \displaystyle \prod_{i=n..2}\displaystyle\frac{2}{i}$.

Значок в виде большой буквы $\prod$ означает произведение. А индексы под значком показывают, какие элементы нужно перемножить.

Если расписать формулу для нашего примера, получится:

При $n=10$ $p \approx 1.4 \times 10^{-4}$, а при $n=20$ $p \approx 1.1 \times 10^{-13}$.

Вряд ли такое будет часто встречаться на практике.

Рассмотрим сложность в лучшем случае. Что будет, каждый раз выбор опорного элемента будет уменьшать подзадачу в 2 раза?

Для оценки сложности алгоритма воспользуемся основной теоремой о рекурсии:

$T(n) = T\displaystyle \left ( \frac {n}{2} \right ) + O(n)$.

При идеальном разбиении на каждом шаге подзадача вдвое меньше задачи, то есть $b = 2$.

Коэффициент $d = 1$, так как операция разделения массива на два подмассива имеет сложность $O(n)$. Получаем, что $\log_b a = \log_2 1 = 0 < 1.$ Это соответствует первому случаю в основной теореме о рекурсии. То есть $T(n) = O(n)$.

Гоша: Хорошо, я понял. Худший случай в алгоритме поиска k-й порядковой статистики — $O(n^2)$, и он маловероятен. В лучшем случае алгоритм работает за линейное время. А что насчёт среднего случая?

Тимофей: Сейчас узнаешь. Назовём подходящим такой элемент $k$, индекс $L$ которого в отсортированном массиве принадлежит отрезку $\displaystyle \left [ \frac{1}{4S}; \frac{3}{4S}\right ]$, где $S$ — длина массива.

Вероятность $p$, что элемент $k$ окажется подходящим равна $\displaystyle\frac{1}{2}$. Ведь отрезок $\displaystyle \left [ \frac{1}{4S}; \frac{3}{4S}\right ]$ занимает половину длины массива.

То есть в среднем каждая вторая попытка приведёт к удачному разбиению.

При удачном разбиении размеры получившихся подмассивов составят не менее $\displaystyle \frac{1}{4}$ и не более $\displaystyle\frac{3}{4}$ от исходного. Значит, хорошее разбиение уменьшает размер задачи как минимум в $\displaystyle \frac{4}{3}$.

Так как удачной в среднем будет каждое второе разбиение, можно сделать вывод, что в среднем за каждые две попытки размер задачи станет меньше хотя бы в $\displaystyle \frac{4}{3}$ раза.

Посчитаем число $Y$, равное общему количеству сравнений:

$2n + \displaystyle \frac{3}{4}\times 2n + \displaystyle \left( \frac{3}{4} \right)^2 \times 2n + ... = 2n \times \left ( \displaystyle 1 + \frac{3}{4} + \left( \frac{3}{4} \right)^2 + ... \right)$

Каждое слагаемое в сумме определяет количество сравнений до того, как размер задачи уменьшится в$\displaystyle \frac{4}{3}$ раза по сравнению с текущим. Умножаем на 2, так как в среднем это будет происходить за 2 попытки.

Второй множитель — сумма бесконечно убывающей геометрической прогрессии.

Для подсчёта суммы воспользуемся формулой:

$S_n = \displaystyle \frac{b_1}{1-q}$.

$b_1$ — первый член геометрической прогрессии. В нашем примере он равен $1$.

$q$ — знаменатель геометрической прогрессии. Он показывает, как от члена на позиции $n$ перейти к члену на позиции $n+1$.

$q = \displaystyle \frac{b_{n+1}}{b_n}$.

В нашем примере $q = \displaystyle \frac{3}{4}$.

Подставив $b_1$ и $q$ в формулу, получим сумму равную 4. Тогда число $Y = 2n \times 4 = 8n$, что равно $O(n)$.

Мы считали сумму бесконечно убывающей прогрессии. На самом деле число слагаемых будет конечным. То есть в результате получится, что $Y$ меньше, чем $8n$. Но даже в случае равенства можно сделать вывод, что сложность будет линейной.

Получим:

$T(n) \leq Y = 8n = O(n) \rightarrow T(n) = O(n)$.

Для доказательства можно также воспользоваться основной теоремой о рекурсии.

$T(n) \leqslant T\left(\displaystyle\frac{3}{4} n\right)+O(n) \rightarrow O(n)$.

Этот случай в основной теореме о рекурсии соответствует сложности $O(n)$.

Гоша: Спасибо! Теперь ясно, почему алгоритм поиска k-й порядковой статистики на практике работает быстро. Кажется, эти рассуждения применимы и для быстрой сортировки, да?

Тимофей: Да, рассуждения для алгоритма быстрой сортировки очень похожи.

Можно также воспользоваться идеей с хорошим разбиением, при котором опорный элемент попадает в центральные 50 % элементов разделяемого массива. Удачной, также как для алгоритма поиска k-ой порядковой статистики, в среднем будет каждая вторая попытка.

Таким образом, всего для получения $k$ удачных разбиений - то есть таких, чтобы опорный элемент $k$ раз оказался среди подходящих элементов, в среднем потребуется $2k$ рекурсивных вызовов. То есть в среднем глубина рекурсии не превышает $2\times \log_{\frac{3}{4}}(n)$, что равно $O(\log n)$.

А так как при каждом рекурсивном вызове выполняется не более $O(n)$ операций, общая сложность алгоритма получится $O(n \log n)$.

Гоша: Теперь я знаю, почему быстрая сортировка на практике работает эффективно и почему её используют в стандартных библиотеках языков программирования.

Тимофей: Да, на практике этот алгоритм достаточно эффективен.

Однако есть такие последовательности, на которых алгоритм будет работать квадратичное время. Они называются killer - последовательностями (англ. killer-sequence).

Например, при выборе первого или последнего элемента массива в качестве опорного отсортированная последовательность будет killer - последовательностью.

Но вероятность наступления таких событий достаточно маленькая.

Гоша: Но ведь быстрая сортировка используется в стандартных библиотеках многих языков программирования. Получается, что алгоритм иногда может работать квадратичное время?

Тимофей: Нет, такие случаи предусмотрели. Например, в С++ есть такая оптимизация. Если в процессе сортировки превышен некоторый коэффициент при $n \log n$, то работа алгоритма завершается. И к работе подключается пирамидальная сортировка. Она гарантированно отсортирует данные за $O(n \log n)$. Про эту сортировку я расскажу в другой раз.