1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 16
Текст из файла (страница 16)
По-видимому, простейший способ сделать это — найти наименьший элемент, исследуя всю последовательность и затем меняя местами наименьший элемент с первым. Процесс повторяется на остальных и — ! элементах, и это повторение приводит к тому, что второй наименьший элемент оказывается на втором месте. Повторение процесса на остальных и — 2, и — 3, ..., 2 элементах сортирует всю последовательность. Зтот алгоритм приводит к рекуррентным уравнениям О при п=1, Т (л) = Т(п — !)+и — 1 при и ) 1 (2,7) Гй.
К. РАЗРАВОТКА ЭФФЕКТИВНЫХ АЛГОРИТМОВ для числа сравнений, произведенных между сортируемыми элементами, Решением для (2.7) служит Т(п)=п(п — 1)/2, что составляет О (и*). Хотя этот алгоритм можно считать рекурсивным применением приема"разделяй и властвуй" с разбиением задачи на неравные части, он не эффективен для больших а. Для разработки асимптотически эффективного алгоритма сортировки надо позаботиться о сбалансированности. Вместо того чтобы разбивать задачу размера п на две подзадачи, одна из которых имеет размер 1, а другая — размер л — 1, надо разбить ее на две подзадачи с размерами примерно л/2. Это выполняется методом, известным как сортировка слиянием.
Рассмотрим последовательность целых чисел хь х„..., х„. Снова предположим для простоты, что п есть степень числа 2. Один из способов упорядочить эту последовательность — разбить ее на две подпоследовательности хо хм ..., Хвг, и хмм]+ О хвФ упо рядочить каждую из них и затем слить их. Под "слиянием" мы понимаем объединение двух уже упорядоченных последовательностей в одну упорядоченную последовательность.
Алгоритм 2.4. Сортировка слиянием Вход. Последовательность чисел хв, х„..., х„, где и — степень числа 2. Вьиод. Последовательность ун ум..., у„, являющаяся перестановкой входа н удовлетворяющая неравенствам у,(~,(...( ~~в Малод. Применим процедуру СЛИЯНИЕ(5, Т), входом которой служат две упорядоченные последовательности 5 и Т, а выходом — последовательность элементов из В и Т, расположенных в порядке неубывания, Поскольку 8 и Т сами упорядочены, СЛИЯНИЕ требует сравнений не больше, чем сумма длин 5 и Т без единицы. Работа этой процедуры состоит в выборе большего из наибольших элементов, остающихся в 5 и Т, и в последующем удалении выбранного элемента.
В случае совпадения можно отдавать предпочтение последовательности 8. ргоседиге СОРТ(1, 1): 11 1=1' (пеп Тейп х, е!зе Ьед(п т — (1+1 — 1)(2; ге1нгп СЛИЯНИЕ(СОРТ(1, т), СОРТ(я+1, 1)) Ркс. 2ЛВ. Сортировка сввквксн. ьа динамическое пэоггкммиэозкнив Кроме того, применяется процедура СОРТ(1, 1) (рис. 2.14), сортирующая подпоследовательность хь х,+„..., хэ в предположении, что она имеет длину 2е для некоторого А= О. Для сортировки данной последовательности х„х„..., х„вызывается процедура СОРТ(1, и). С) Подсчет числа сравнений в алгоритме 2 4 приводит к рекуррент- ным уравнениям О прн л=1, Т(п) = 2Т(а/2)+л — 1 при и) 1, решением которых по теореме 2.1 является Т(а)=0(п 1ой и).
Для больших и сбалансированность размеров подзадач дала значительную выгоду. Аналогичный анализ показывает, что общее время работы процедуры СОРТ, затрачиваемое не только на сравнения, также есть 0(п!ой и). 2.6. ДИНАМИЧЕСНОЕ ПРОГРАММИРОВАНИЕ Рекурсивная техника полезна, если аадачу можно разбить на подзадачи за разумное время, а суммарный размер подзадач будет небольшим. Из теоремы 2.1 вытекает, что если сумма размеров подзадач равна ап для некоторой постоянной а)1, то рекурсивный алгоритм, вероятно, имеет полиномиальную временную сложность. Но если очевидное разбиение задачи размера л сводит ее к и задачам размера л — 1, то рекурсивный алгоритм, вероятно, имеет экспоненциальную сложность.
В этом случае часто можно получить более эффективные алгоритмы с помощью табличной техники, называемой динамическим программированием. Динамическое программирование, в сущности, вычисляет решение для всех подзадач. Вычисление идет от малых подзадач к ббльшим, и ответы запоминаются в таблице. Преимущество этого метода состоит в том, что раз уж подзадача решена, ее ответ где-то хранится и никогда не вычисляется заново.
Эту технику легко понять на простом примере. Рассмотрим вычисление произведения п матриц М=М,хМ,х... хМ„, где М~ — матрица с гс т строками и г~ столбцами. Порядок, в котором эти матрицы перемножаются, может существенно сказаться на общем числе операций, требуемых для вычисления М, независимо от алгоритма, применяемого для умножения матриц. Пример 2Л. Предположим, что умножение (равд)-матрицы на (д х г)-матрицу требует рог операций, как это и бывает в "обычном" ГЛ.
В. РАЭРАВОТКА ЭФФЕКТИВНЫХ АЛГОРИТМОВ алгоритме, и рассмотрим произведение М= М, х М, х М, хМ, [10 х 20) [20 х 501 [50 х Ц [1 х 1001 где размеры каждой матрицы М~ указаны в скобках. Если вычислять М в порядке (2.6) Процесс перебора всех порядков, в которых можно вычислить рассматриваемое произведение и матриц, с целью минимизировать число операций имеет зкспоненциальную сложность (упр. 2.31), что при больших п практически неприемлемо.
Однако динамическое программирование приводит к алгоритму сложности 0(пе). Пусть ты — минимальная сложность вычисления Мч Х М ~+, Х... Х Мп 1((Я(п. Очевидно, что О, (2.9) М1)ч! (т,а+та+т,у+г,,гаг~), если ! >1. -=( ~<А</ Здесь тд — минимальная сложность вычисления М'=М, х хМч+,х...
х Мто а ти+, г — минимальная сложность вычисления М" = М„, х М„, х . ° ° х М . Третье слагаемое равно сложности умножения М' на М". Заметим, что М' — матрица размера г~,хгд, а М" — матрица размера г„х Ьед(п 1. 1ог ! -! оп!11 л до глн — 0; 2. 1ог 1 -1 пи!11 п — 1 до 3. 1ог 1 — 1 оп!11 л — 1 бо Ьей!и 4 1 -!+1; 5. ти М1Р( (т~а+т у+г; и ганг ) Ч<а<! епд; 6. тнг11е т„ епд Рие. 2лз. Алгоритм динамического протраммиропания для определения порядка умножения матриц. М,х(м,х(м,х М,)), то потребуется 125 000 операций, тогда как вычисление М в порядке (М,х(М,хм,))хм, занимчет лишь 2200 операций. Д 2.2.
ЭПИЛОР Рнс. 2дб. Сложности вычисления произведений М;ХМ2+,Х...ХМР Хгр В (2.9) утверждается, что и;> Ц)1) — наименьшая из сумм этих трех членов по всем возможным значениям й, лежащим между е' и 1 — 1. При динамическом программировании лен вычисляются в порядке возрастания разностей нижних индексов. Начинают с вычисления тн для всех 1, затем т, 2+2 для всех 1, потом ип 2+2 и т. д.
При этом т,в и те~2 х в (2.9) будут уже вычислены, когда мы приступим к вычислению лен. Это следует из того, что при 1(и<1 разность 1 — 1 должна быть больше й — 1, а также и 1 — (5+1). Приведем теперь алгоритм. Алгоритм 2.5. Алгоритм динамического программирования для вычисления порядка, минимизирующего сложность умножения цепочки из а матриц М,)(М2)(...ХМ, Вход.
ЄЄ..., г„, где Ре 2 и ге — числа строк и столбцов матрицы Мп Выход. Минимальная сложность умножения матриц Ме в предположении, что для умножения (рхд)-матрицы на (дхг)-матрицу требуется рог операций. Метод. Алгоритм, приведенный на рис. 2.15. Пример 2.8, Если применить этот алгоритм к цепочке из четырех матриц (2.8), где г„..., ге равны соответственно 1О, 20, 50, 1, 100, то в результате вычислений получатся значения т~~, приведенные на рис.
2.15. Таким образом, минимальное число операций, требуемых для вычисления этого произведения, равно 2 200. Порядок, в котором можно произвести эти умножения, легко определить, приписав каждой клетке таблицы то значение й, на котором достигается минимум в (2.9). (:) 2.9. ЭПИЛОГ В этой главе мы изложили ряд основных методов, которыми пользуются при разработке эффективных алгоритмов.
Было показано, как структуры высокого уровня — списки, очереди и стеки— избавляют разработчика алгоритмов от скучной работы (например, ГЛ. 2. РАЗРАБОТКА ЭФФЕКТИВНЫХ АЛГОРИТМОВ с указателями) и позволяют сосредоточиться на общей структуре самого алгоритма. Кроме того, мы увидели, как мощная техника рекурсии и динамического программирования часто приводит к элегантным и естественным алгоритмам.
Мы познакомились также с некоторыми общими приемами, такими, как "разделяй и властвуй" и балансировка. Эти методы, разумеется, не являются единственно доступными, но они принадлежат к числу важнейших. Далее в этой книге мы изложим и другие примеры. Они будут относиться к различным задачам — от выбора подходящего представления до нахождения разумного порядка выполнения операций, Возможно, важнейшим принципом хорошего разработчика алгоритмов должно быть чувство неудовлетворенности. Разработчику следует изучать задачу с разных точек зрения, пока он не убедится, что получил алгоритм, наиболее подходящий для его целей.
УПРАЖНЕНИЯ 2.1. Выберите реализацию для дважды связанного списка. Напишите алгоритм на Упрощенном Алголе для вставки и удаления элемента. Убедитесь, что ваши программы работают, когда надо удалить первый и(или) последний элементы и когда список пуст. 2.2. Напишите алгоритм для обращения порядка элементов в списке. Докажите, что он работает правильно. 2.3. Напишите алгоритмы, реализующие операции ЗАТОЛКНУТЬ, ВЫТОЛКНУТЬ, ВПИСАТЬ и ВЫПИСАТЬ, упомянутые в равд. 2.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
