Ожидаемое время быстрой сортировки

Читаю доказательство теоремы:

Алгоритм быстрой сортировки сортирует последовательность н элементы в О ( н бревно ⁡ н ) ожидаемое время.

Доказательство таково:

Для простоты временного анализа предположим, что все элементы С различны.

Это предположение максимизирует размеры С 1 и С 3 , и, следовательно, максимизировать среднее время, затрачиваемое на рекурсивные вызовы (QUICKSORT( С 1 ), БЫСТРАЯ СОРТИРОВКА( С 3 )).

Позволять Т ( н ) — ожидаемое время, необходимое БЫСТРОЙ СОРТИРОВКЕ для сортировки последовательности н элементы.

Четко, Т ( 0 ) "=" Т ( 1 ) "=" б для некоторой константы б .

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

Затем два рекурсивных вызова QUICKSORT (QUICKSORT( С 1 ), БЫСТРАЯ СОРТИРОВКА( С 3 )) имеют ожидаемое время Т ( я − 1 ) и Т ( н − я ) , соответственно.

С я с равной вероятностью принимает любое значение между 1 и н , а остаток QUICKSORT( С явно требует времени с н для некоторой константы с , имеем отношение:

(1) Т ( н ) ≤ с н + 1 н ∑ я "=" 1 н [ Т ( я − 1 ) + Т ( н − я ) ] ,  для  н ≥ 2

Алгебраические манипуляции ( 1 ) урожаи

(2) Т ( н ) ≤ с н + 2 н ∑ я "=" 0 н − 1 Т ( я )

Покажем, что для н ≥ 2 , Т ( н ) ≤ к н бревно е ⁡ н , где к "=" 2 с + 2 б и б "=" Т ( 0 ) "=" Т ( 1 ) .

Для основы н "=" 2 , Т ( 2 ) ≤ 2 с + 2 б следует непосредственно из ( 2 ) .

Для шага индукции напишите ( 2 ) как

(3) Т ( н ) ≤ с н + 4 б н + 2 н ∑ я "=" 2 н − 1 к я бревно е ⁡ я

С я бревно е ⁡ я вогнута вверх, легко показать, что

(4) ∑ я "=" 2 н − 1 я бревно е ⁡ я ≤ ∫ 2 н Икс бревно е ⁡ Икс г Икс ≤ н 2 бревно е ⁡ н 2 − н 2 4

Замена ( 4 ) в ( 3 ) урожаи

(5) Т ( н ) ≤ с н + 4 б н + к н бревно е ⁡ н − к н 2

С н ≥ 2 и к "=" 2 с + 2 б , следует, что с н + 4 б / н ≤ к н / 2 .

Таким образом Т ( н ) ≤ к н бревно е ⁡ н следует ( 5 ) .

Как мы получили отношение ( 1 ) ?

Заранее спасибо.

Редактировать:

Можете ли вы объяснить мне эту фразу:

«Это предположение максимизирует размеры С 1 и С 3 , и, следовательно, максимизировать среднее время, затрачиваемое на рекурсивные вызовы (QUICKSORT( С 1 ), БЫСТРАЯ СОРТИРОВКА( С 3 )). "

?

Почему это максимизирует среднее время, затрачиваемое на рекурсивные вызовы?

Ответы (1)

Быстрая сортировка сводится к:

  1. Выбор точки поворота

  2. Разделить большой список на список «меньше сводного» С 1 и список «больше сводного» С 2

  3. Сортировать С 1 и С 2 отдельно, результат вызова С 1 ′ и С 2 ′ .

  4. Объединить С 1 ′ и С 2 ′ и перейти к окончательному отсортированному списку С ′ .

    Случайный выбор опорной точки — это постоянное время. Отсюда следует, что

Т ( н ) ≤ [ Шаг 2 ] + [ Шаг 3 ] + [ Шаг 4 ]

Шаг 2 занимает а н время для некоторой постоянной а . Вы просто делаете проход по списку, сравниваете его с опорным и добавляете его в любой С 1 или С 2 . Шаг 4 занимает не более б н время по менее очевидным причинам. Следовательно, шаги 2 и 4 занимают не более с н время для постоянного с .

Шаг 3 остается. Выражение

1 н ∑ я "=" 1 н [ Т ( я − 1 ) + Т ( н − я ) ]

это среднее значение Т ( я − 1 ) + Т ( н − я ) общий я , и это рекурсивный шаг, сортировка двух строго меньших списков. Следовательно, приведенная выше сумма представляет собой среднее время, необходимое для выполнения шага 3.

В заключение, весь процесс занимает менее с н + 1 н ∑ я "=" 1 н [ Т ( я − 1 ) + Т ( н − я ) ] время.

Хорошо. И почему Т ( н ) меньше или равно сумме этих двух значений?
Отредактировано для уточнения. Дайте мне знать, если у вас есть дополнительные вопросы.
Используем ли мы среднее значение Т ( я − 1 ) + Т ( н − я ) потому что мы хотим найти ожидаемое время быстрой сортировки?
Кроме того, когда мы выбираем опорную точку случайным образом, это также постоянное время?
Ага. На самом деле, наихудший случай для быстрой сортировки О ( н 2 ) , когда у вас есть список, отсортированный в обратном порядке, потому что вам нужно выбрать н поворачивается, и каждый внутренний шаг будет О ( н ) время также.
Ха-ха, это хороший вопрос. Теоретически получение случайного числа — это постоянное время. Псевдослучайные числа также вычисляются быстро. На практике компьютер может выполнять некоторые странные вычисления, и получение чего-то «настоящего» случайного с помощью генератора случайных чисел может занять много времени. О ( н ) или О ( н 2 ) время, где н это максимальное значение, которое вы хотите.
Я понимаю! Спасибо за объяснение! У меня есть и другой вопрос... В пункте "покажем, что для н ≥ 2 , Т ( н ) ≤ к н бревно е ⁡ н , где к "=" 2 с + 2 б и б "=" Т ( 0 ) "=" Т ( 1 ) ", почему мы берем это к ? И почему мы берем базу е для бревно ?
Он выбрал это к просто работая в обратном направлении; он знает это к должно быть не более чем некоторой константой в зависимости от характера вопроса.
Одним из результатов теории алгоритмов является то, что основание журнала не имеет значения при рассмотрении временной сложности. Если что-то равно O (log_2 (n)), то это также O (log_e (n)) и O (log_100 (n)) и т. д. Таким образом, он использует log_e (то же самое, что и ln), поэтому интеграл упрощается. .
Не могли бы вы объяснить мне также это предложение: «Это предположение максимизирует размеры С 1 и С 3 , и, следовательно, максимизировать среднее время, затрачиваемое на рекурсивные вызовы (QUICKSORT( С 1 ), БЫСТРАЯ СОРТИРОВКА( С 3 )). "? Почему это максимизирует среднее время, затрачиваемое на рекурсивные вызовы?
Привет! Как насчет ожидаемой глубины? Почему это О ( бревно ⁡ н )
Ожидаемое время быстрой сортировки
СпросиСетьПолитика конфиденциальности1y, 0v