Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 16
Текст из файла (страница 16)
Поскольку логарифмическая функция растет медленнее, чем линейная, то для достаточно большого количества входных элементов производительность алгоритма сортировки методом слияния, время работы которого равно 0 (ге 1к п), превзойдет производительность алгоритма сортировки методом вставок, время работы которого в наихудшем случае равно 6 (пз). Правда, можно и без упомянутой теоремы интуитивно понять, что решением рекуррентного соотношения (2.1) является выражение Т(п) = 1В (п1к и).
Перепишем уравнение (2.1) в таком виде: Т(п) = (2.2) 2Т (гг/2) + сп при и > 1, где константа с обозначает время, которое требуется для решения задачи? размер который равен 1, а также удельное (приходящееся на один элемент) время, требуемое для разделения и сочетанияэ. Маловероятно, чтобы одна и та же константа представляла и время, необходимое для решения задачи, размер который равен 1, и приходящееся на олин элемент время, в течение которого выполняются этапы разбиения и объединения.
Чтобы обойти эту проблему, достаточно предположить, что с — максимальный из перечисленных промежутков времени. В таком случае мы получим верхнюю границу времени работы алгоритма. Если же в качестве с выбрать наименьший из всех перечисленных промежутков времени, то в результате решения рекуррентного соотношения получим нижнюю границу времени работы алгоритма. Принимая во внимание, что обе границы имеют порядок и!й п, делаем вывод, что время работы алгоритма ведет себя, как 6 (и 1я и) . 80 Часть 1.
Основы Т(п) Т(п/2) Т(пЩ Т(п/4) Т(л/4) Т(п/4) Т(п/4) в) б) /~ сп/4 сп/4 сп/4 сл/4 -------~ сл 1~ 1~ (~ 1~ с с с с с ... с с --3л сл Всего: сл )а л+ сл Рис. 2.5. Построение дерева рекурсии для уравнения Т (и) = 2Т (гг/2) + сп Процесс решения рекуррентного соотношения (2.2) проиллюстрирован на рис. 2.5. Для удобства предположим, что и равно степени двойки. В части а упомянутого рисунка показано время Т(п), представленное в части б в виде эквивалентного дерева, которое представляет рекуррентное уравнение. Корнем зтого дерева является слагаемое сп.(стоимость верхнего уровня рекурсии), а два Глава 2. Приступаем к изучению поддерева, берущих начало от корня, представляют две меньшие рекуррентные последовательности Т(п/2). В части в показан очередной шаг рекурсии.
Время выполнения каждого из двух подузлов, находящихся на втором уровне рекурсии, равно сп/2. Далее продолжается разложение каждого узла, входящего в состав дерева, путем разбиения их на составные части, определенные в рекуррентной последовательности. Так происходит до тех пор, пока размер задачи не становится равным 1, а время ее выполнения — константе с. Получившееся в результате дерево показано в части г. Дерево состоит из 18 и+ 1 уровней (т.е. его высота равна 18 п), а каждый уровень дает вклад в полное время работы, равный сп. Таким образом, полное время работы алгоритма равно си18п+ сп, что соответствует О (п 18 и). После того как дерево построено, длительности выполнения всех его узлов суммируются по всем уровням. Полное время выполнения верхнего уровня равно сп, следующий уровень дает вклад, равный с(п/2) + с(п/2) = сп.
Ту же величину вклада дают и все последующие уровни. В общем случае уровень г (если вести отсчет сверху) имеет 2' узлов, каждый из которых дает вклад в общее время работы алгоритма, равный с (и/2'), поэтому полное время выполнения всех принадлежащих уровню узлов равно 2'с (и/2') = сп.
На нижнем уровне имеется и узлов, каждый из которых дает вклад с, что в сумме дает время, равное сп. Полное количество уровней дерева на рис. 2.5 равно 18 и+ 1. Это легко понять из неформальных индуктивных рассуждений. В простейшем случае, когда п = 1, имеется всего один уровень. Поскольку 18 1 = О, выражение 18 п+ 1 дает правильное количество уровней. Теперь в качестве индуктивного допущения примем, что количество уровней рекурсивного дерева с 2' узлами равно 18 2'+1 = 1+1 (так как для любого г выполняется соотношение 18 2' = г). Поскольку мы предположили, что количество входных элементов равняется степени двойки, то теперь нужно рассмотреть случай для 2'+з элементов. Дерево с 2'ч 1 узлами имеет на один уровень больше, чем дерево с 2' узлами, поэтому полное количество уровней равно (г + 1) + 1 = 1й 2ьь1 + 1.
Чтобы найти полное время, являющееся решением рекуррентного соотношения (2.2), нужно просто сложить вклады от всех уровней. Всего имеется 18 и+ 1 уровней, каждый из которых выполняется в течение времени сп, так что полное время равно сп (18 п + 1) = сп 18 и + сп. Пренебрегая членами более низких порядков и константой с, в результате получаем О (п!бп).
Упражнения 2.3-1. Используя в качестве образца рис. 2.4, проиллюстрируйте работу алгоритма сортировки методом слияний для массива А = (3, 41, 52, 26, 38, 57, 9, 49). Часть 1. Основы 82 2.3-2. Перепишите процедуру Мекол так, чтобы в ней не использовались сиг- нальные значения. Сигналом к остановке должен служить тот факт, что все элементы массива Т, или массива гт скопированы обратно в массив А, после чего в этот массив копируются элементы, оставшиеся в непустом массиве. 2.3-3. Методом математической индукции докажите, что если п равно степени двойки, то решением рекуррентного уравнения 2 при п = 2, 2Т (и/2) + п при п = 2ь, й > 1 является Т(п) = п18п. 2.3-4. Сортировку вставкой можно представить в виде рекурсивной последо- вательности следующим образом.
Чтобы отсортировать массив А [1..п], сначала нужно выполнить сортировку массива А [1..п — 1], после чего в этот отсортированный массив помещается элемент А [и]. Запишите рекуррентное уравнение для времени работы этой рекурсивной версии алгоритма сортировки вставкой. 2.3-5. Возвращаясь к задаче поиска (см. упражнение 2.1-3), нетрудно заметить, что если последовательность А отсортирована, то значение среднего элемента этой последовательности можно сравнить с искомым значением о и сразу исключить половину последовательности из дальнейшего рассмотрения. Двоичный (бинарный) поиск (Ьшагу зеагсЬ) — это алгоритм, в котором такая процедура повторяется неоднократно, что всякий раз приводит к уменьшению оставшейся части последовательности в два раза. Запишите псевдокод алгоритма бинарного поиска (в итерационном нлн рекурсивном виде).
Докажите, что время работы этого алгоритма в наихудшем случае возрастает как 6 (18 и). 2.3-6. Обратите внимание, что в цикле иЬйе в строках 5-7 процедуры 1ызпк- трон Войт в разделе 2.1, используется линейный поиск для просмотра (в обратном порядке) отсортированного подмассива А,[1..7' — 1]. Можно ли использовать бинарный поиск (см. упражнение 2.3-5) вместо линейного, чтобы время работы этого алгоритма в наихудшем случае улучшилось и стало равным Э(п18и)? * 2.3-7. Пусть имеется множество о, состоящее из и целых чисел, и отдельное целое число х; необходимо определить, существуют ли во множестве Я два элемента, сумма которых равна х.
Разработайте алгоритм решения этой задачи, время работы которого возрастало бы с увеличением п как 9 (и 18 и). Глава 2. Приступаем к изучению 83 Задачи 2-1. Сортировка вставкой для небольших подмассивов, возникающих при сортировке слиянием Несмотря на то, что с увеличением количества сортируемых элементов время сортировки методом слияний в наихудшем случае растет как 6 (п18п), а время сортировки методом вставок — как 9 (пз), благодаря постоянным множителям для малых и сортировка методом вставок выполняется быстрее. Таким образом, есть смысл испольювать сортировку методом вставок в процессе сортировки методом слияний, когда подзадачи становятся достаточно маленькими. Рассмотрите модификацию алгоритма сортировки, работающего по методу слияний, когда п(М подмассивов длины Й сортируются методом вставок, после чего они объединяются с помощью обычного механизма слияния.
Величина к должна быть найдена в процессе решения задачи. а) Покажите, что п()с подмассивов, в каждом из которых находится Й элементов, в наихудшем случае можно отсортировать по методу вставок за время 9 (пк). б) Покажите, что в наихудшем случае время, требуемое для объединения этих подмассивов, равно О (и 18 (п(И) ). в) Допустим, что время работы модифицированного алгоритма в наихудшем случае равно О (п)с+ п18 (и/)с)). Определите максимальное асимптотическое (в О-обозначениях) значение )с как функцию от п, для которого асимптотическое время работы модифицированного алгоритма равно времени работы стандартного алгоритма сортировки методом слияния. г) Как следует выбирать параметр )с на практике? 2-2.
Корректность пузырьковой сортировки Пузырьковый метод — популярный алгоритм сортировки. В его основе лежит многократная перестановка соседних элементов, нарушающих порядок сортировки: ВОВВьезОкт1А) 1 1ог 1 — 1 го 1епдй[А] 2 до 1ог д' ~ — 1епдй[А] йотгпГо г' + 1 3 йо 11' А[з] < А[з — 1] 4 Гпеп Поменять местами А[з] А[у — 1] а) Пусть А' — выходной массив, полученный в результате работы процедуры ВинЕЬЕЗОКТ(А). Чтобы доказать, что этот алгоритм работает Часть !.
Основы 84 корректно, нужно доказать, что он выполняется в течение конечного времени и что выполняются неравенства А'[1] < А'[2] « А'[и], (2.3) где и = !еидй [А]. Что еще необходимо доказать, чтобы стало очевидно, что в ходе работы алгоритма Виввьвзокт действительно выполняется сортировка входного массива? В следующих двух пунктах доказываются неравенства (2.3). б) Дайте точную формулировку инварианта цикла !'ог в строках 2-4, и докажите, что он сохраняется. Доказательство должно иметь такую же структуру доказательства инварианта цикла, которая использовалась в аналогичных доказательствах в данной главе.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
