Я проходил анализ быстрой сортировки в книге Алгоритмов Седжвика. Он создает следующее рекуррентное отношение для числа сравнений в быстрой сортировке при сортировке массива из N различных элементов.
Мне тяжело понять это ... Я знаю, что для любого элемента требуется 1 / N вероятность того, что он станет стержнем, и что если k становится стержнем, то в левом подмассиве будет k-1 элементов и правый подмассив. массив будет иметь Nk элементов.
1. Как стоимость разбиения становится N + 1? Требуется ли сравнение N + 1 для разбиения?
2. Седжвик говорит, что для каждого значения k, если вы сложите их, вероятность того, что элемент разделения равен k + стоимость для двух подмассивов, вы получите приведенное выше уравнение.
- Может ли кто-нибудь объяснить это так, чтобы те, у кого меньше знаний по математике (я), могли понять?
- В частности, как вы получаете второй член в уравнении?
- Что именно означает этот термин?
Ответы:
Функция стоимости
C
для быстрой сортировки состоит из двух частей. Первая часть - это стоимость разбиения массива на две «половины» (половинки не обязательно должны быть одинакового размера, следовательно, кавычки). Вторая часть - это стоимость сортировки этих двух половинок.(N + 1)
Термин фактически конденсированной термин, и исходит из условийЭто стоимость разбиения в быстрой сортировке:
N-1
сравнивается со значением сводки, и еще 2 сравниваются из-за некоторых граничных условий в разбиении.Вторая часть уравнения состоит из затрат на сортировку двух «половинок» по обе стороны от значения поворота
k
.После выбора значения разворота у вас останется две несортированные «половины». Стоимость сортировки этих «половинок» зависит от их размера и проще всего описывается как рекурсивное применение функции стоимости
C
. Если стержень является наименьшим изN
значений, затраты на сортировку каждой из двух «половин» равны соответственноC(0)
иC(N-1)
(стоимость сортировки массива с 0 элементами и стоимость сортировки одного сN-1
элементами). Если стержень является пятым наименьшим, то стоимость для сортировки каждого из двух «половинок» равна соответственноC(5)
иC(N-6)
(стоимость для сортировки массива с элементами 5 и стоимость сортировки один сN-6
элементами). И аналогично для всех других значений пивота.Но сколько стоит сортировка этих двух «половинок», если вы не знаете значения пивота? Это сделано, беря стоимость для каждого возможного значения центра и умножая это на шанс, что это конкретное значение повышается.
Поскольку каждое значение поворота одинаково вероятно, шанс выбрать конкретное значение поворота возможен,
1/N
если у вас естьN
элементы. Чтобы понять это, подумайте о том, чтобы бросить кости. При правильной игре в кости вероятность того, что каждая сторона окажется лицом вверх, равна, поэтому шанс бросить 1 равен 1/6.В сочетании это дает сумму суммирования, где для каждого возможного значения k пивота стоимость (
C(k-1) + C(N-k)
) умножается на шанс (1/N
)Дальнейший вывод формулы суммирования в вопросе к
2N lnN
названию в названии занимает слишком много математики, чтобы объяснить здесь подробно, но он основан на понимании того, что стоимость сортировки массиваN
элементов (C(N)
) может быть выражена в терминах сортировки массивN-1
элементов (C(N-1)
) и коэффициент, который прямо пропорционаленN
.источник
Кажется, что N + 1 как число сравнений для шага разбиения является ошибкой в книге. Вам необходимо выяснить для каждого из N-1 непивотных элементов, является ли он меньше или больше, чем сводный, что требует одного сравнения; Таким образом, всего N – 1 сравнений, а не N + 1. (Рассмотрим простейший случай, N = 2, то есть один стержень и один другой элемент: абсолютно нет места для трех сравнений между двумя элементами.)
Рассмотрим случай, когда выбранный стержень оказывается наименьшим элементом (k = 1). Это означает, что массив разделен на пустую часть слева (нет элементов, которые меньше, чем сводная), и часть справа, которая содержит все элементы, кроме сводной (все остальные элементы больше, чем сводная). ). Это означает, что подзадачи, которые вы теперь хотите решить рекурсивно, имеют размеры 0 и N – 1 (k – 1 и N – k) соответственно и требуют сравнений C (0) и C (N – 1); таким образом, всего C (0) + C (N – 1).
Если ось оказывается вторым наименьшим элементом (k = 2), размеры подзадачи равны 1 и N – 2 (k – 1 и N – k; один элемент слева, потому что он единственный меньше, чем стержень). Таким образом, рекурсивное решение этих подзадач требует C (1) + C (N – 2) сравнений. И так далее, если ось является третьим наименьшим элементом, четвертым и т. Д. Это выражения в числителях.
Поскольку поворот выбирается случайным образом из числа N элементов, каждый случай (поворот наименьший, поворот наименьший и т. Д.) Происходит с равной вероятностью 1 / N. Вот откуда N в знаменателях.
источник