Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 21
Текст из файла (страница 21)
Обозначим время работы г1нп-Млх1мг1м-811влккм' над подмассивом из и элементов как Т(п). Для начала строка 1 выполняется за константное время. Базовый случай п = 1 прост; строка 2 выполняется за константное время, так что Т(1) = 9(1) . (4.5) При и > 1 осуществляется рекурсивный случай. Строки 1 и 3 выполняются за константное время. Каждая из подзадач, решаемых в строках 4 и 5, работает с подмассивами, состоящими из и/2 элементов (наше предположение о том, что размер исходной задачи представляет собой степень 2, гарантирует, что и/2 является целым), так что мы тратим время Т(п/2) на решение каждой из них. Поскольку мы должны решить две подзадачи (для левого и правого подмассивов), вклад в общее время работы от строк 4 и 5 составляет 2Т(п/2).
Как мы уже видели, вызов Епчп-МАх-Скозз1нО-811влккАу в строке б требует времени ев(п). Строки 7 — 11 выполняются за время В(1). Итак, для рекурсивного случая мы имеем Т(п) = 9(1) + 2Т(п/2) + В(п) + 9(1) = 2Т(п/2) +9(п) . (4.6) 1ъаеа к Разделай и юаствуй Объединив уравнения (4.5) и (4.6), мы получаем рекуррентное соотношение для времени работы Т(п) процедуры Рпчп-Млх[мим-Бивлкклу: 9 (1), если и = 1, Т(п) = 2Т(п/2) + 9(п), если и ) 1 . (4.7) Упражнения 4,1.1 Что возвращает процедура Рпчп-Млх~мпм-бивлкклу, когда все элементы А отрицательны? 4.1.2 Напишите псевдокод для решения задачи поиска максимального подмассива ме- тодом грубой силы.
Ваша процедура должна выполняться за время 9(пз). 4.1.3 Реализуйте и метод грубой силы, и рекурсивный алгоритм на своем компьютере. Каким оказывается размер задачи точки пересечения по, в которой рекурсивный алгоритм превосходит алгоритм грубой силы? Далее измените базовый случай рекуррентного алгоритма, применяя алгоритм грубой силы при размере задачи, не превосходящем по. Меняет ли это точку пересечения? 4.1.4 Предположим, что мы меняем определение задачи поиска максимального под- массива, позволяя конечному результату быть пустым массивом и полагая, что сумма значений пустого массива равна нулю.
Как бы вы изменили любой алго- ритм, не допускающий решения в виде пустого массива, чтобы такой результат а виде пустого подмассива стал возможным? Это рекуррентное соотношение такое же, как и рекуррентное соотношение (4А) для сортировки слиянием. Как мы узнаем, познакомившись в разделе 4.5 с основным методом, это рекуррентное соотношение имеет решение Т(п) = 9(п!бп). Вы можете также обратиться к дереву рекурсии на рис.
2.5, чтобы понять, почему решение указанного рекуррентного соотношения должно иметь вид Т(п) = 6(п )б и). Таким образом, мы видим, что метод "разделяй и властвуй" дает алгоритм, который оказывается асимптотически быстрее метода грубой силы. Сортировка слиянием, а теперь еще и поиск максимального подмассива демонстрируют нам, насколько мощным может оказаться метод "разделяй и властвуй".
Иногда он дает асимптотически самые быстрые алгоритмы для решения задачи, но иногда можно найти еше лучшие алгоритмы. Как показано в упр. 4А.5, задача поиска максимального подмассива решается за линейное время и не использует метод "разделяй и властвуй*'. Часть 1 Осмовы 4.1.5 Воспользуйтесь приведенными далее идеями для разработки нерекурсивного алгоритма поиска максимального подмассива за линейное время. Начните с левого конца массива и двигайтесь вправо, отслеживая найденный к данному моменту максимальный подмассив.
Зная максимальный подмасснв массива А[1 .. з], распространите ответ на поиск максимального подмассива, заканчивающегося индексом з + 1, воспользовавшись следующим наблюдением: максимальный подмассив массива А[1 ..1+ Ц представляет собой либо максимальный подмассив массива А[1 .. 2], либо подмассив А[1 ..
1+ 1] для некоторого 1 < 1 < 1+ 1. Определите максимальный подмассив вида А[1 .. з + 1] за константное время, зная максимальный подмассив, заканчивающийся индексом 1. 4.2. Алгоритм Штрассена для умножения матриц Если вы уже встречались с матрицами, то наверняка знаете, как их перемножать. (В противном случае прочтите раздел Г.1 в приложении Г.) Если А = [а; ) и В = (6, ) представляют собой квадратные матрицы размером и х п, то элементы с; их произведения С = А В определяются для 1, з = 1, 2,..., и следующим образом: и с; =~~ аы.бь а=1 (4.8) Нам нужно вычислить пз элементов матрицы, каждый из которых представляет собой сумму и значений.
Приведенная далее процедура получает в качестве входных данных и х и-матрицы А и В и перемножает их, возвращая их и х и- произведение С. Мы считаем, что каждая матрица имеет атрибут тоша, указывающий количество строк матрицы. 80ОАкк-МАтк1х-М~л.тп'и'(А, В) 1 п = А.гоюз 2 Пусть С вЂ” новая матрица размером и х и 3 Гог 1 = 1 то и 4 Гог з' = 1 то п 5 со=О 6 1огlс = 1топ 7 с;. = с; +ага Ьь. 8 гетпгп С Процедура ЯОилкк-МАтк1х-Мш.тичх работает следующим образом.
Цикл Гог в строках 3 — 7 вычисляет элементы каждой строки г', а в пределах данной строки 1 цикл Гог в строках 4 — 7 вычисляет каждый из элементов с, для каждого столбца ). Строка 5 инициализирует с, значением 0 в начале вычисления суммы Глава 4.
Разделяй а влаезавуй 101 из уравнения (4.8), и каждая итерация цикла лог в строках 6 и 7 добавляет еще один член из (4.8). Из-за того, что каждый из циклов в тройной вложенности циклов Ког выполняет ровно и итераций, а каждое выполнение строки 7 занимает константное время, вся процедура 8011Акп-МАтк1х-М1л.т1ил выполняется за время лэ(из).
На первый взгляд, можно решить, что любой алгоритм умножения матриц должен выполняться за время 11(и ), поскольку естественное определение умножения матриц требует именно этого количества умножений. Однако это не так: имеется способ умножения матриц за время о(из). В этом разделе вы познакомитесь с замечательным рекурсивным алгоритмом Штрассена для умножения матриц размером и х и.
Его время работы составляет лг(и1кт), как будет показано в разделе 4.5. Поскольку 18 7 лежит между 2.80 и 2.81, алгоритм Штрассена выполняется за время О(из а1), что асимптотически лучше простой процедуры 800Аке-МАтк!х-М1л.т1Рьу. Ап Ага В Вп Вгг С Сп Сгг, (49) так что уравнение С = А В можно переписать как Сп С1г Ап А1г Вп Вгг (4 0) Уравнение (4.10) соответствует четырем уравнениям Сп = Ап Вп + Агг . Вгг, Сгг = Ап . Вгг + Агг . Вгг, Сгг = Агг Вп + Агг. Вщ Сгг = Агг В1г+Агг Вгг (4.11) (4.12) (4.13) (4.14) В каждом из этих четырех уравнений присутствуют два умножения матриц раз- мером и/2 х и/2 и сложение полученных произведений размером и/2 х и/2. Эти уравнения можно использовать для создания прямолинейного рекурсивного алгоритма "разделяй и властвуй".
Простой алгоритм "разделяй и властвуй" Для простоты при использовании алгоритма "разделяй и властвуй" для вычисления произведения матриц С = А В будем считать, что в каждой из этих матриц размером и х и значение и представляет собой точную степень 2. Мы делаем зто предположение потому, что на каждом шаге разделения мы будем разбивать матрицы размером и х и на четыре матрицы размером и/2 х и/2, и то, что и представляет собой точную степень 2, гарантирует, что пока и > 2, размерность и/2 является целым числом.
Допустим, что мы разделяем каждую из матриц А, В и С на четыре матрицы размером и/2 х и/2 Часыь 1 Основы 811САке-МАтк!х-М~л.т1Р1х-Кеспк$1че(А, В) 1 и = А.гома 2 Пусть С вЂ” новая матрица размером и х и 3 И'и==1 4 с11 = а1! Ь!! 5 е!зе разбиение А, В и С как в (4.9) 6 Сп = ЯЯСАке-МАтк1х-М~лтичл-Кеспкяче(А!1,В1!) + 81)иАке-МАтк1Х-М~л.т1их-Кесикяче(А!з, Вз!) 7 С1з = БЯСАке-МАтк!х-М$л.т1Р1л"-Кеспкз!че(А!1, Вш) + Б! САке-МАтк1х-М~л.т1РЕУ-Кеспкз1че(Ани Вяз) 8 Сз! = БОСАке-МАтк!Х-М~л.тпчл-Кеспкяче(Аз1, В„) + ЯОиАке-МАтк1х-М~лт1ил-Кеспкяче(Аги Вз1) 9 Сзз = БОСАке-МАтк!х-М$л.т1РЕУ-Кеспкз!че(Аз1, В!з) + Я!7САке-МАтк!х-Мпет1РЕУ-Кеспкз!че(Азз, Вяз) 10 гетигп С Этот псевдокод скрывает одну важную тонкость реализации. Как мы разбиваем матрицы в строке 5? Если мы создаем 12 новых матриц размером и/2 х и/2, то мы платим за это временем !В(из), затраченным на копирование элементов матриц.
В действительности матрицы можно разбивать без копирования. Весь фокус заключается в вычислениях индексов. Мы определяем подматрицу как диапазон индексов строк и диапазон индексов столбцов исходной матрицы. В результате мы представляем подматрицу немного не так, как исходную матрицу, и эта тонкость не указана явно. Преимущество заключается в том, что поскольку мы можем указать подматрицу с помощью индексов, выполнение строки 5 требует только времени Э(1) (хотя, как мы увидим в дальнейшем, асимптотическое поведение общего времени работы не зависит от того, будем ли мы копировать матрицы или разбивать их без привлечения дополнительной памяти).
Теперь выведем рекуррентное соотношение, описывающее время работы процедуры Я!2САке-МАтк1Х-М[л.т1Реч-Кеспкз1че. Пусть Т(и) — время, необходимое для умножения двух матриц размером и х и с использованием этой процедуры. В базовом случае, когда и = 1, мы выполняем только одно скалярное умножение в строке 4, так что Т(1) = вз(1) . (4.15) При и ) 1 осуществляется рекуррентный случай. Как говорилось, разбиение матриц в строке 5 требует при использовании вычисления индексов времени !В(1). В строках 6-9 мы восемь раз рекурсивно вызываем процедуру Б!2САкеМАтк1Х-М~л.тпчл'-Кеспкяче.
Поскольку каждый рекурсивный вызов перемножает две матрицы размером и/2 х и/2, его вклад в общее время работы составляет Т(и/2), а все восемь вызовов выполняются за время 8Т(и/2). Следует также учесть четыре сложения матриц в строках 6 — 9. Каждая из этих матриц содержит из/4 элементов, так что каждое из сложений матриц требует времени св(из). Поскольку количество матричных сложений является константой, общее время Рвала К Разделяй а властвуй сложения в строках 6 — 9 равно О(пг).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
