Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 14
Текст из файла (страница 14)
Это скорость роста (гаСе оГ йгоук1)з), или порядок роста (оггзег оГ яготчт)з), времени работы, который и интересует нас на самом деле. Таким образом, во внимание будет приниматься только главный член формулы (т.е, в нашем случае апз), поскольку при больших п членами меньшего порядка можно пренебречь. Кроме того, постоянные множители при главном члене также будут игнорироваться, так как для оценки вычислительной эффективности алгоритма с входными данными большого объема они менее важны, чем порядок роста.
Таким образом, время работы Далее в книге строгий термин "математическое ожидание" некоторой величины зачастую для простоты изложения заменяется термином "ожидаемое значение", например, "ожидаемое время работы алгоритма" означает "математическое ожидание времени работы алгоритма". — Прим.
ред. Глава 2. Приступаем к изучению 71 алгоритма, работающего по методу вставок, в наихудшем случае равно 6 [пз) (пронзносится "тета от и в квадрате"). В этой главе О-обозначения используются неформально; их строгое определение приводится в главе 3. Обычно один алгоритм считается эффективнее другого, если время его работы в наихудшем случае имеет более низкий порядок роста. Из-за наличия постоянных множителей и второстепенных членов эта оценка может быть ошибочной, если входные данные невелики. Однако если объем входных данных значительный, то, например, алгоритм О [пз) в наихудшем случае работает быстрее, чем а„,,,рн,„, О гпз) Упражнения 2.2-1.
Выразите функцию пз/1000 — 100пз — 100п + 3 в О-обозначениях. 2.2-2. Рассмотрим сортировку элементов массива А, которая производится так. Сначала определяется наименьший элемент массива А, который ставится на место элемента А [1], затем производится поиск второго наименьшего элемента массива А, который ставится на место элемента А [2]. Этот процесс продолжается для первых п — 1 элементов массива А. Запишите псевдокод этого алгоритма, известного как сортировка амбарам (зе!есйоп зоп). Какой инвариант цикла сохраняется для этого алгоритма? Почему его достаточно выполнить для первых и — 1 элементов, а не для всех и элементов? Определите время работы алгоритма в наилучшем и наихудшем случаях и запишите его в О-обозначениях.
2.2-3. Рассмотрим алгоритм линейного поиска (см. упражнение 2.1-3). Для скольких элементов входной последовательности в среднем нужно произвести проверку, если предполагается, что все элементы массива с равной вероятностью могут иметь искомое значение? Что происходит в наихудшем случае? Чему равно время работы алгоритма линейного поиска в среднем и в наихудшем случае (в 6-обозначениях)? Обоснуйте ваш ответ. 2.2-4. Каким образом можно модифицировать почти каждый алгоритм, чтобы получить оптимальное время работы в наилучшем случае? 2.3 Разработка алгоритмов Есть много методов разработки алгоритмов.
В алгоритме, работающем по методу вставок, применяется инкрементный подход: располагая отсортированным подмассивом А [1.. у — 1], мы помещаем очередной элемент А [1] туда, где он должен находиться, в результате чего получаем отсортированный подмассив А [1..7]. Часть 1. Основы 72 В данном разделе рассматривается альтернативный подход к разработке алгоритмов, известный как метод разбиения (" разделяй и властвуй"). Разработаем с помощью этого подхода алгоритм сортировки, время работы которого в наихудшем случае намного меньше времени работы алгоритма, работающего по методу включений. Одно из преимуществ алгоритмов, разработанных методом разбиения, заключается в том, что время их работы часто легко определяется с помощью технологий, описанных в главе 4.
2.3.1 Метод декомпозиции Многие полезные алгоритмы имеютрекурсивную структуру: для решения данной задачи онн рекурсивно вызывают сами себя один или несколько раз, чтобы решить вспомогательную задачу, имеющую непосредственное отношение к поставленной задаче. Такие алгоритмы зачастую разрабатываются с помогцью метода декомлозиции, нлн разбиения: сложная задача разбивается на несколько более простых, которые подобны исходной задаче, но имеют меньший объем; далее эти вспомогательные задачи решаются рекурсивным методом, после чего полученные решения комбинируются с целью получить решение исходной задачи. Парадигма, лежащая в основе метода декомпозиции "разделяй и властвуй", на каждом уровне рекурсии включает в себя три этапа.
Разделение задачи на несколько подзадач. Покорение — рекурсивное решение этих подзадач. Когда объем подзадачи достаточно мал, выделенные подзадачи решаются непосредственно. Комбинирование решения исходной задачи из решений вспомогательных задач. Алгоритм сортировки слиянием (щегле зоп) в большой степени соответствует парадигме метода разбиения. На интуитивном уровне его работу можно описать таким образом.
Разделение: сортируемая последовательность, состоящая из и элементов, разбивается на две меньшие последовательности, каждая из которых содержит и/2 элементов. Покорение: сортировка обеих вспомогательных последовательностей методом слияния. Комбинирование: слияние двух отсортированных последовательностей для получения окончательного результата. Рекурсия достигает своего нижнего предела, когда длина сортируемой последовательности становится равной 1.
В этом случае вся работа уже сделана, поскольку любую такую последовательность можно считать упорядоченной. Глава 2. Приступаем к изучению 73 Основная операция, которая производится в процессе сортировки по методу слияний, — это объединение двух отсортированных последовательностей в ходе комбинирования (последний этап). Это делается с помощью вспомогательной процедуры Мексе(А,р,д, т), где А — массив, а р, о и т — индексы, нумерующис элсменты массива, такие, что р < о < т.
В этой процедуре предполагается, что элементы подмассивов А [р.А)] и А [д+ 1..т] упорядочены. Она сливает эти два подмассива в один отсортированный, элементы которого заменяют текущие элементы подмассива А [р..т]. Для выполнения процедуры Мексе требуется время О (и), где п = т — р+ 1— количество подлежащих слиянию элементов. Процедура работает следующим образом. Возвращаясь к наглядному примеру сортировки карт, предположим, что на столе лежат две стопки карт, обращенных лицевой стороной вниз. Карты в каждой стопке отсортированы, причем наверху находится карта наименьшего достоинства. Эти две стопки нужно обьединить в одну выходную, в которой карты будут рассортированы и также будут обращены рубашкой вверх. Основной шаг состоит в том, чтобы из двух младших карт выбрать самую младшую, извлечь ее из соответствующей стопки (при этом в данной стопке верхней откажется новая карта) и поместить в выходную стопку.
Этот шаг повторяется до тех пор, пока в одной из входных стопок не кончатся карты, после чего оставшиеся в другой стопке карты нужно поместить в выходную стопку. С вычислительной точки зрения выполнение каждого основного шага занимает одинаковые промежутки времени, так как все сводится к сравнению достоинства двух верхних карт. Поскольку необходимо выполнить, по крайней мере, и основных шагов, время работы процедуры слияния равно 9 (п).
Описанная идея реализована в представленном ниже псевдокоде, однако в нем также есть дополнительное ухищрение, благодаря которому в ходе каждого основного шага не приходится проверять, является ли каждая из двух стопок пустой. Идея заключается в том, чтобы поместить в самый низ обеих объединяемых колод так называемую сигнальную карту особого достоинства, что позволяет упростить код.
Для обозначения сигнальной карты используется символ оо. Не существует карт, достоинство которых больше достоинства сигнальной карты. Процесс продолжается до тех пор, пока проверяемые карты в обеих стопках не окажутся сигнальными. Как только это произойдет, это будет означать, что все несигнальные карты уже помещены в выходную стопку. Поскольку заранее известно„что в выходной стопке должно содержаться ровно т — р+ 1 карта, выполнив такое количество основных шагов, можно остановиться: МЕКбЕ(А, р, о, т) 1 п1 — о — р+1 2 пз — т — о 3 Создаем массивы А[1..п1+ 1] н В[1..пэ + 1] Часть !.
Основы 4 !огз -1!оззз 5 з!о Цз] — А[р+ з — 1] 6 !ог 7' — 1 го пз 7 з1о Л[7'] — А[9+,у] 8 з" [зз! + 1] — оо 9 Л[ззя + 1] ~ — оо !О з — 1 !! 7' -1 !2 !ог !з — р го т !3 Йо ИЬ[з] < Л[7] !4 т!зеп А[!з] — Ь[з] !5 з~ — з+1 16 е!яе А[)з] — Л[Я !7 7 -7+1 Подробно опишем работу процедуры Мексн. В строке 1 вычисляется длина пз подмассива А [р..д], а в строке 2 — длина пз подмассива А [д+ 1..г]. Далее в строке 3 создаются массивы Ь (" левый" — "!ей") и Л ("правый" — "г!8!з!"), длины которых равны пз + 1 и пз + 1 соответственно.
В цикле !ог в строках 4 и 5 подмассив А [р..з7] копируется в массив Ь [1..ззз], а в цикле !ог в строках б и 7 подмассив А [д+ 1..г] копируется в массив Л [1..пя]. В строках 8 и 9 последним элементам массивов з' и Л присваиваются сигнальные значения. Как показано на рис. 2.3, в результате копирования и добавления сигнальных карт получаем массив з. с последовательностью чисел (2, 4, 5, 7, оо) и массив Л с последовательностью чисел (1,2,3,6,оо). Светло-серые ячейки массива А содержат конечные значения, а светло-серые ячейки массивов Е и Л вЂ” значения, которые еше только должны быть скопированы обратно в массив А. В светло-серых ячейках находятся исходные значения из подмасснва А [9..16] вместе с двумя сигнальными картами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
