Алгоритмы - построение и анализ (1021735), страница 13
Текст из файла (страница 13)
° Характер поведения "усредненного" времени работы часто ничем не лучше поведения времени работы для наихудшего случая. Предположим, что последовательность, к которой применяется сортировка методом вставок, Часть 1. Основы 70 сформирована случайным образом. Сюлько времени понадобится, чтобы определить, в какое место подмассива А [1..7' — Ц следует поместить элемент А [7]? В среднем половина элементов подмассива А [1..7' — Ц меньше, чем А [7'], а половина — больше его.
Таким образом, в среднем нужно проверить половину элементов подмассива А [1.. 7' — Ц, поэтому г приблизительно равно у/2. В результате получается, что среднее время работы алгоритма является квадратичной функцией от количества входных элементов, т.е. характер этой зависимости такой же, как и для времени работы в наихудшем случае. В некоторых частных случаях нас будет интересовать среднее время работы алгоритма, или его математическое ожиданиеб. В главе 5 будет продемонстрирован метод вероятностного анализа, позволяющий определить ожидаемое время работы.
Однако при анализе усредненного времени работы возникает одна проблема, которая заключается в том, что не всегда очевидно, какие входные данные для данной задачи будут "усредненными". Часто делается предположение, что все наборы входных параметров одного и того же обьема встречаются с одинаковой вероятностью. На практике это предположение может не соблюдаться, однако иногда можно применять рандомизированные алгоритмы, в юторых используется случайный выбор, и это позволяет провести вероятностный анализ.
Порядок возрастания Для облегчения анализа процедуры 1мзпкт~ом Яокт были сделаны неюторые упрощающие предположения. Во-первых, мы проигнорировали фактическое время выполнения каждой инструкции, представив эту величину в виде некоторой константы с;. Далее мы увидели, что учет всех этих констант дает излишнюю информацию: время работы алгоритма в наихудшем случае выражается формулой апз + Ьп + с, где а, Ь, и с — некоторые константы, зависящие от стоимостей с;ч Таким образом, мы игнорируем не только фактические стоимости команд, но и их абстрактные стоимости сч Теперь введем еще одно абстрактное понятие, упрощающее анализ. Это скорость роста (гаСе оГ йгоук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— количество подлежащих слиянию элементов. Процедура работает следующим образом. Возвращаясь к наглядному примеру сортировки карт, предположим, что на столе лежат две стопки карт, обращенных лицевой стороной вниз. Карты в каждой стопке отсортированы, причем наверху находится карта наименьшего достоинства.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
