Структуры данных и алгоритмы (1021739), страница 66
Текст из файла (страница 66)
Длинапути от корня к листу равна количеству сравнений, которые необходимо сделать, чтобы получить то упорядочение, которое соответствует данному листу, исходя из определенного начального списка элементов L. Поэтому длина самого длинного пути от корняк листу — это нижняя граница количества шагов (количество сравнений ключей), вы-256ГЛАВА 8.
СОРТИРОВКАполняемых алгоритмом сортировки в самом худшем случае. Но также не надо забывать, что, кроме сравнения ключей, алгоритм выполняет и другие операции.Рассмотрим, какова же может быть длина путей в двоичном дереве с k листьями.Двоичное дерево, в котором все пути имеют длину р или меньше, может иметь 1 корень, 2 узла на первом уровне, 4 узла на втором уровне и далее 2' узлов на уровне I.Поэтому наибольшее число листьев 2Р на уровне р, если нет узлов, выше этого уровня. Отсюда следует, что двоичное дерево с k листьями должно иметь путь длиной неменее logfe. Если положить k = n\, то получим, что любой алгоритм сортировки, использующий для упорядочивания п элементов только сравнения значений ключей, всамом худшем случае должен выполняться за время, не меньшее Q(log(ra!)).Какова степень роста величины log(n!)? По формуле Стирлинга п\ можно достаточно точно аппроксимировать функцией (п/е)п, где е — 2.7183...
— основание натурального логарифма. Поскольку log((ra/e)") = п logn - п loge = п logra - 1.44л, то отсюда получаем, что log(nl) имеет порядок п logn. Можно получить более простуюнижнюю границу, если заметить, что л! является произведением не менее и/2 сомножителей, каждое из которых не превышает л/2. Поэтому га! > (л/2)л/2. Следовательно, log(nl) > (n/2)log(n/2) = (ra/2)logra - л/2. Из любой приведенной оценки вытекает, что сортировка посредством сравнений требует в самом худшем случае временипорядка Q(ra logn).Анализ времени выполнения в среднемМожно ожидать, что алгоритм, который в самом худшем случае выполняется завремя О(п logra), в среднем будет иметь время выполнения порядка О(п) или, покрайней мере, меньшее, чем О(п logra).
Но это не так, что мы сейчас и покажем, оставляя детали доказательства читателю в качестве упражнения.Надо доказать, что в произвольном двоичном дереве с k листьями средняя глубина листьев не менее logfc. Предположим, что это не так, и попробуем построитьконтрпример двоичного дерева Т с k листьями, у которого средняя глубина листьевбыла бы меньше logft. Поскольку дерево Т не может состоять только из одного узла(в этом случае невозможен контрпример, так как утверждение выполняется — средняя глубина равна 0), пусть k > 2. Возможны две формы двоичного дерева Т, которые показаны на рис. 8.6./слистьева,< k листьевРис.
8.6. Возможные формы двоичного дерева ТДерево на рис. 8.6,а не может быть контрпримером с минимальной среднейглубиной листьев, поскольку дерево с корнем в узле лх имеет столько же листьев,что и дерево Т, но его средняя глубина меньше. Дерево на рис. 8.6,6 не нарушает8.6. ВРЕМЯ ВЫПОЛНЕНИЯ СОРТИРОВОК СРАВНЕНИЯМИ257требования к контрпримеру. Пусть средняя глубина листьев поддерева Т\ составляет logfej, а средняя глубина листьев поддерева Т2 — logfea- Тогда средняя глубиналистьев дерева Т равна-\log(k1) + \-^-\l0g(k2) + l.Поскольку hi + Й2 = k, то последнее выражение можно переписать так:(8.13)Легко проверить, что при ki = k2 = ft/2 выражение (8.13) принимает значениеlogfe. Теперь читатель должен показать, что выражение (8.13) при выполнении условия ki + k2 = k имеет минимум, когда fti = k2.
Это несложное упражнение для читателя, знакомого с дифференциальным исчислением. Так как минимум выражения(8.13) равен logfe, то можно считать доказанным, что контрпример дерева Т со средней глубиной листьев, меньшей чем logft, не существует.8.7. Порядковые статистикиЗадача вычисления порядковых статистик заключается в следующем: дан список из п записей и целое число k, необходимо найти ключ записи, которая стоит всписке, отсортированном в возрастающем порядке, в fe-й позиции.
Для краткости этузадачу будем называть "задачей нахождения ft-й порядковой статистики". Специальные случаи этой задачи возникают при k = 1 (нахождение минимального элемента),k = п (нахождение максимального элемента) и, если п нечетно, k = (п + 1)/2(нахождение медианы).В некоторых случаях решение задачи вычисления порядковых статистик находится за линейное время. Например, нахождение минимального элемента (как имаксимального) требует времени порядка О(п). Как упоминалось при изучении пирамидальной сортировки, если k < n/logn, тогда для нахождения ft-й порядковойстатистики можно построить кучу (за время порядка О(п)) и затем выбрать из нееk наименьших элементов за время О(п + k logn) = О(и).
Подобным образом приk > п - n/logn также можно найти k-ю порядковую статистику за время О(п).Вариант быстрой сортировкиПо-видимому, самым быстрым в среднем способом нахождения ft-й порядковойстатистики является рекурсивное применение процедуры, основанной на методе быстрой сортировки. Назовем эту процедуру select (выбор).
Процедура select(i. j, k) находит ft-й элемент среди элементов A[i], ..., A[j], которые взяты из некоторого большого массива А[1], ..., А[п]. Процедура select выполняет следующие действия.1.2.Назначает опорный элемент, скажем и.Используя процедуру partition из листинга 8.7, разделяет элементы A[i\, ..., A[f]на две группы. В первой группе A[i], ..., А[т - 1] значения ключей всех записейменьше v, во второй группе А[т], ..., A[f\ — равны или больше v.3. Если k < т — i, тогда А-й элемент находится в первой группе и к ней снова применяется процедура select(i, т - 1, k).
Если k > т - i, тогда вызывается процедура select(m, j, k - т + i).Рано или поздно вызов процедуры select(i, j, k) будет сделан для элементовA[i], ..., A[j], имеющих одинаковые значения ключей (и поэтому скорее всего будет i = j ) . Значение ключа этих элементов и будет искомым значением fe-й порядковой статистики.258ГЛАВА 8. СОРТИРОВКАТак же, как и метод быстрой сортировки, процедура select (так как она описана2выше) в самом худшем случае потребует времени не менее О(л ). Например, если припоиске минимального элемента в качестве опорного элемента всегда брать наибольшее из возможных значений ключей, то получим для этой процедуры время выпол2нения порядка О(л ).
Но в среднем процедура select работает значительно быстрее,чем алгоритм быстрой сортировки, в среднем она выполняется за время О(л). Принципиальная разница между этими алгоритмами заключается в том, что когда процедура быстрой сортировки вызывается два раза, процедура select в аналогичной ситуации вызывается только один раз. Можно провести анализ процедуры select темиже методами, которые применялись при анализе алгоритма быстрой сортировки, ночтобы избежать сложных математических выкладок, здесь мы ограничимся толькоинтуитивными соображениями, показывающими среднее время выполнения процедуры select.
Эта процедура повторно вызывает себя на подмножестве, которое является только частью того множества, для которого она вызывалась на предыдущемшаге. Сделаем умеренное предположение, что каждый вызов этой процедуры осуществляется на множестве элементов, которое составляет 9/10 того множества, для которого был произведен предыдущий вызов процедуры. Тогда, если обозначить черезТ(п) время, затрачиваемое процедурой select на множестве из п элементов, для некоторой константы с будем иметь.Т(п)<Т(-^п) + сп.(8.14)Используя технику из следующей главы, можно показать, что решением неравенства (8.14) будет Т(п) = О(п).Линейный метод нахождения порядковых статистикЧтобы гарантировать для процедуры, подобной select, в самом худшем случаевремя выполнения порядка О(п), необходимо показать, что за линейное время можновыбрать такой опорный элемент, который разбивает множество элементов на дваподмножества, размер которых не больше некоторой фиксированной доли исходногомножества.
Например, решение неравенства (8.14) показывает, что если опорныйэлемент не меньше (га/10)-го порядкового элемента и не больше (9га/10)-го порядкового элемента, тогда множество, для которого вызывается процедура select, разбивается на подмножества, не превышающие 9/10 исходного множества, и это гарантирует линейное время в самом худшем случае.Нахождение "хорошего" опорного элемента можно осуществить посредством следующих двух шагов.1.Выполняется разделение п элементов на группы по 5 элементов, оставляя в стороне группу из 1 - 4 элементов, не вошедших в другие группы.
Каждая группаиз 5 элементов сортируется любым алгоритмом в порядке возрастания и берутсясредние элементы из каждой группы. Всего таких средних элементов будет [л/5].2. Используя процедуру select, находится медиана этих средних элементов. Если[л/5] — четно, то берется элемент, наиболее близкий к середине. В любом случаебудет найден элемент, стоящий в позиции [(п + 5)/10] отсортированного спискасредних элементов.Если среди записей не слишком много таких, значения ключей которых совпадаютсо значением опорного элемента, тогда значение опорного элемента достаточно далекоот крайних значений ключей.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
