Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013), страница 11

На практике это предположение может не соблюдаться, однако иногда можно применять рандамизироеаииые алгоритмы, в которых используется случайный выбор, и это позволяет провести вероятностный анализ ожидаемого времени работы алгоритма. Более детально мы рассмотрим рандомизированные алгоритмы в главе 5 и некоторых последующих главах. Порядок роста Для облегчения анализа процедуры 1мзпктюм-Бонт были сделаны некоторые упрощающие предположения.

Вначале мы проигнорировали фактическую стоимость выполнения каждой инструкции, представив эту величину в виде некоторой константы с,. Далее мы увидели, что учет всех этих констант дает излишнюю информацию: время работы алгоритма в наихудшем случае выражается формулой апз + 6п + с, где а, 6 и с — некоторые константы, зависящие от стоимостей с,. Таким образом, мы игнорируем не только фактические стоимости команд, но и их абстрактные стоимости с;ч Теперь введем еще одно абстрактное понятие, упрощающее анализ. Это скорость роста (гаге оТ йтовч)з), или иоридок роста (оп)ег оТ йгосебз), интересующего нас времени работы.

Таким образом, во внимание будет приниматься только главный член формулы (т.е. в нашем случае апз), поскольку при больших значениях и членами меньшего порядка можно пренебречь. Кроме того, постоянный множитель при главном члене также будет игнорироваться, так как для оценки вычислительной эффективности алгоритма с входными данными большого обьема они менее важны, чем порядок роста. В случае сортировки вставкой, когда мы игнорируем члены более низкого порядка и коэффициент при старшем члене, мы остаемся с единственным множителем пз из старшего члена. Таким образом, время работы алгоритма, работающего по методу вставок, в наихудшем случае равно В(пз) (произносится "тета от п в квадрате*'). В этой главе сЭ-обозначения используются неформально; строго мы определим их в главе 3.

Обычно один алгоритм рассматривается как более эффективный по сравнению с другим, если время его работы в наихудшем случае имеет более низкий порядок роста. Из-за константных множителей и членов более низкого порядка алгоритм с более высоким порядком роста может выполняться для небольших входных данных быстрее, чем алгоритм с более низким порядком роста. Но для достаточно больших входных данных алгоритм О(пз), например, будет в наихудшем случае работать быстрее алгоритма с О(пз).

Упражнения г.г.1 Выразите функцию п~/1000 — 100п~ — 100п + 3 в й-обозначениях. Часть 2 Основы г.г.г Рассмотрим сортировку элементов массива А, которая выполняется следующим образом. Сначала определяется наименьший элемент массива А, который ставится на место элемента А]1]. Затем производится поиск второго наименьшего элемента массива А, который ставится на место элемента А]2]. Этот процесс продолжается для первых и — 1 элементов массива А. Запишите псевдокод этого алгоритма, известного как сортировка выбором (зе1есйоп зоп).

Какой инвариант цикла сохраняется для этого алгоритма? Почему его достаточно выполнить для первых п — 1 элементов, а не для всех п элементов? Определите время работы алгоритма в наилучшем и наихудшем случаях и запишите его в Й-обозначениях. г.г.з Вновь обратимся к алгоритму линейного поиска (см. упр. 2.1.3). Для скольких элементов входной последовательности в среднем нужно произвести проверку, если предполагается, что все элементы массива с равной вероятностью могут иметь искомое значение? Что происходит в наихудшем случае? Чему равно время работы алгоритма линейного поиска в среднем и в наихудшем случаях в 9- обозначениях? Обоснуйте свой ответ.

г.г.б Каким образом можно модифицировать почти каждый алгоритм, чтобы получить оптимальное время работы в наилучшем случае? 2.3. Разработка алгоритмов У нас имеется богатый набор методов разработки алгоритмов. В случае сортировки вставкой мы использовали инкрементный подход: имея отсортированный подмассив А]1 ..? — 1], мы вставляем один элемент А[?] в соответствующее место, получая отсортированный подмассив А]1 .. ?]. В этом разделе мы рассмотрим альтернативный подход, известный как метод декомпозиции, илн метод "разделяй и властвуй", который мы детально изучим в главе 4.

Мы используем подход "разделяй и властвуй" для разработки алгоритма сортировки, время работы которого в наихудшем случае оказывается гораздо меньшим, чем время работы сортировки вставкой. Одно из преимуществ алгоритмов "разделяй и властвуй" заключается в том„что зачастую оказывается очень легко определить время работы такого алгоритма с применением методики, которая будет описана в главе 4.

2.3.1. Метод декомпозиции Многие полезные алгоритмы имеют рекурсивную структуру: для решения поставленной задачи они рекурсивно вызывают сами себя один или несколько раз, решая вспомогательные подзадачи, тесно связанные с основной задачей. Такие алгоритмы зачастую разрабатываются с помощью метода декомпозиции, или метода "разделяй и власгнвуй": сложная задача разбивается на несколько простых, 53 Глава д Приступаем К изучению которые подобны исходной задаче, но имеют меньший объем; далее эти вспомогательные задачи решаются рекурсивным методом, после чего полученные решения комбинируются для получения решения исходной задачи.

Парадигма, лежащая в основе метода декомпозиции "разделяй и властвуй", на кюклом уровне рекурсии включает в себя три шага. Разделение задачи на несколько подзадач, которые представляют собой меньшие экземпляры той же задачи.

Властвование над подзадачами путем их рекурсивного решения. Если размеры подзадач достаточно маны, такие подзадачи могут решаться непосредственно. Комбинирование решений подзадач в решение исходной задачи. Алгоритм сортировки слиянием (шегйе зон) точно следует парадигме "разделяй и властвуй'*. Интуитивно он работает следующим образом. Разделение.

Делим и-элементную сортируемую последовательность на две подпоследовательности по и/2 элементов. Властвование. Рекурсивно сортируем эти две подпоследовательности с использованием сортировки слиянием. Комбинирование. Соединяем две отсортированные подпоследовательности для получения окончательного отсортированного ответа. Рекурсия достигает своего нижнего предела, когда длина сортируемой последовательности становится равной 1. В этом случае вся работа уже сделана, поскольку любая такая последовательность уже является упорядоченной. Ключевая операция, которая производится в процессе сортировки по методу слияний, — это объединение двух отсортированных последовательностей в ходе комбинирования (последний этап). Это делается с помощью вызова вспомогательной процедуры ргосебцге Мнкпп(А,р, о, г), где А — массив, а р, з1 и г— индексы, нумерующие элементы массива, такие, что р < д < г.

В этой процедуре предполагается, что элементы подмассивов А~р .. д) и А[д+ 1 .. г] упорядочены. Она сливаелв эти два подмассива в один отсортированный, элементы которого заменяют текущие элементы подмассива А1р .. г~). Для выполнения процедуры Мякин требуется время 9(п), где п = г — р+ 1— общее количество подлежащих слиянию элементов. Процедура работает следующим образом. Возвращаясь к наглядному примеру сортировки карт, предположим, что на столе лежат две стопки карт, обрашенных лицевой стороной вниз.

Карты в каждой стопке отсортнрованы, причем наверху находится карта наименьшего достоинства. Эти две стопки нужно объединить в одну выходную, в которой карты будут рассортированы и также будут обрашены рубашкой вверх. Основной шаг состоит в том, чтобы из двух младших карт выбрать самую младшую, извлечь ее из соответствующей стопки (при этом в данной стопке верхней откажется новая карта) и поместить в выходную стопку. Этот шаг повторяется до тех пор, пока в одной из входных стопок не закончатся карты, после чего оставшиеся в другой стопке карты нужно поместить в выходную стопку.

С вычислительной Часть Е. Овсовы точки зрения выполнение каждого основного шага занимает одинаковые промежутки времени, так как все сводится к сравнению достоинства двух верхних карт. Поскольку необходимо выполнить по крайней мере п основных шагов, время работы процедуры слияния равно й(п). Описанная идея реализована в представленном ниже псевдокоде, однако в нем также есть дополнительное ухищрение, благодаря которому в ходе каждого основного шага не приходится проверять, является ли каждая из двух стопок пустой.

Мы помещаем в самый низ обеих объединяемых колод так называемую сигнальную карту-ограничитель особого достоинства, что позволяет упростить код. Здесь в качестве сигнального значения используется оо, так что, когда мы встречаем карту достоинством оо, меньшей карты мы не встретим до полного исчерпания обеих стопок. Как только мы встречаем такую карту, это означает, что все несигнальные карты уже помещены в выходную стопку. Поскольку заранее известно, что в выходной стопке должна содержаться ровно т — р+ 1 карта, выполнив соответствующее количество основных шагов, можно остановиться.

МККОВ(А, р, О, т) 1 п1 =о — р+1 2 пз=т — д 3 Пусть Г,[! .. пз + Ц и ГГ(! .. пз + Ц вЂ” новые массивы 4 Гог в' = 1 то пз 5 Ь)1) = А[р+1 — Ц б Гог в' = 1 го пз 7 Я[в'] = А[9+Я 8 Г[п!+ Ц = оо 9 гг[пз+ Ц = оо 10 1=1 11 1=! 12 Гогlс = ргот 13 !ГГ[в] < ГГ[в') 14 А[к) = Г,[!] 15 !=1+1 16 е!яе А[к] = ГГ[Я 17 ! =2+1 Подробно рассмотрим работу процедуры МЕкОЕ. В строке 1 вычисляется длина п1 подмассива А)р .. д], а в строке 2 вычисляется длина пз подмассива А[у + 1 ..