Пытаюсь понять сравнение 2N lnN для быстрой сортировки

Question

Я просматривал анализ быстрой сортировки в книге Седжвика "Алгоритмы".Он создает следующее рекуррентное соотношение для количества сравнений в quicksort при сортировке массива из N различных элементов.

Мне трудно это понять...Я знаю, что для того, чтобы любой элемент стал стержнем, требуется вероятность 1 / N, и что если k станет стержнем, то в левом подмассиве будет k-1 элементов, а в правом подмассиве будет N-k элементов.

1.Каким образом стоимость секционирования становится N+ 1?Требуется ли N + 1 сравнений для выполнения разбиения на разделы?

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

• Может ли кто-нибудь объяснить это так, чтобы те, у кого меньше знаний в математике (я), могли понять?
• В частности, как вы получаете второе слагаемое в уравнении?
• Что именно означает этот термин?

Answer 1

Функция затрат C для быстрой сортировки состоит из двух частей.Первая часть - это стоимость разбиения массива на две "половины" (половины не обязательно должны быть одинакового размера, отсюда и кавычки).Вторая часть - это стоимость сортировки этих двух половинок.

1. Тот Самый (N + 1) термин на самом деле является сокращенным термином и происходит от терминов

   (N - 1) + 2
   

   Это стоимость разбиения на разделы в quicksort: N-1 сравнивается со значением pivot, и 2 дополнительных сравниваются из-за некоторых граничных условий при разбиении.

2. Вторая часть уравнения состоит из затрат на сортировку двух "половинок" по обе стороны от сводного значения k.

   После выбора значения pivot у вас остаются две несортированные "половинки".Стоимость сортировки этих "половинок" зависит от их размера и проще всего описывается как рекурсивное применение функции затрат C.Если стержень является наименьшим из N значения, затраты на сортировку каждой из двух "половинок" соответственно C(0) и C(N-1) (стоимость сортировки массива с 0 элементами и стоимость сортировки одного с N-1 элементы).Если стержень является пятым по величине, то стоимость сортировки каждой из двух "половинок" соответственно равна C(5) и C(N-6) (стоимость сортировки массива из 5 элементов и стоимость сортировки одного с N-6 элементы).И аналогично для всех других сводных значений.

   Но сколько стоит отсортировать эти две "половинки", если вы не знаете значения pivot?Это делается путем взятия стоимости для каждого возможного значения pivot и умножения ее на вероятность выпадения этого конкретного значения.

   Поскольку каждое значение разворота одинаково вероятно, вероятность выбора конкретного значения разворота равна 1/N если у вас есть N элементы.Чтобы понять это, подумайте о том, как бросают кости.При правильном выпадении кубиков вероятность того, что каждая сторона окажется открытой, равна, так что вероятность выпадения 1 равна 1/6.

   В совокупности это дает суммирующий член, где для каждого возможного значения k сводной точки стоимость (C(k-1) + C(N-k)) умножается на вероятность (1/N)

3. Дальнейший вывод формулы суммирования, приведенной в вопросе к 2N lnN в названии слишком много математики, чтобы объяснять здесь подробно, но оно основано на понимании того, что затраты на сортировку массива N элементы (C(N)) может быть выражено в терминах сортировки массива N-1 элементы (C(N-1)) и коэффициент , который прямо пропорционален N.

Answer 2

1. Кажется, что n + 1 как количество сравнений для шага раздела - ошибка в книге. Вам нужно выяснить для каждого из неворотных элементов N-1, независимо от того, меньше или больше, чем у поворота, что требует одно сравнение; Таким образом, N-1 сравнения в общей сложности, а не N + 1. (Рассмотрим простейший случай, n= 2, то есть один поворот и один другой элемент: есть абсолютно нет места для выполнения трех сравнений между двумя элементами.)

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 элементов n, каждый случай (поворот наименьшего, поворот - это второй маленький, и т. Д.) Происходит с равной вероятностью 1 / п. Вот где происходит n в знаменателях.