Алгоритмы - построение и анализ (1021735), страница 15
Текст из файла (страница 15)
Анализ алгоритма сортировки слиянием Псевдокод Мнкон Бокт корректно работает для произвольного (в том числе и нечетного) количества сортируемых элементов. Однако если количество элементов в исходной задаче равно степени двойки, то анализ рекуррентного уравнения упрощается. В этом случае на каждом шаге деления будут получены две подпоследовательности, размер которых точно равен и/2. В главе 4 будет показано, что это предположение не влияет на порядок роста, полученный в результате решения рекуррентного уравнения. Чтобы получить рекуррентное уравнение для верхней оценки времени работы Т (и) алгоритма, выполняющего сортировку и чисел методом слияния, будем Глава 2. Приступаем к изучению 79 рассуждать следующим образом.
Сортировка одного элемента методом слияния длится в течение фиксированного времени. Если и > 1, время работы распреде- ляется таким образом. Разбиение. В ходе разбиения определяется, где находится средина подмассива. Эта операция длится фиксированное время, поэтому Р (п) = 0 (1). Покорение. Рекурсивно решаются две подзадачи, объем каждой из которых составляет гз/2. Время решения этих подзадач равно 2Т (гз/2). Комбинирование. Как уже упоминалось, процедура Мбкгзб в п-элементном подмассиве выполняется в течение времени 9 (гт), поэтому С (и) = с1 (и). Сложив функции Р (гг) и С (и), получим сумму величин О (и) и О (1), которая является линейной функцией от и, те. 0 (и).
Прибавляя к этой величине слагаемое 2Т (гг/2), соответствующее этапу "покорения*'„получим рекуррентное соотношение для времени работы Т (гь) алгоритма сортировки по методу слияния в наихудшем случае: 0 (1) при гь = 1, 2Т(гг/2) + 0(гг) при гг > 1. (2.1) В главе 4 мы ознакомимся с теоремой, с помощью которой можно показать, что величина Т (гг) представляет собой 6 (гз 1я и), где 1к п обозначает 1кз и.
Поскольку логарифмическая функция растет медленнее, чем линейная, то для достаточно большого количества входных элементов производительность алгоритма сортировки методом слияния, время работы которого равно 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 (и/)с)). Определите максимальное асимптотическое (в О-обозначениях) значение )с как функцию от п, для которого асимптотическое время работы модифицированного алгоритма равно времени работы стандартного алгоритма сортировки методом слияния.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
