Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 19
Текст из файла (страница 19)
Рекуррентное соотношение представляет собой уравнение или неравенство, которое описывает функцию через ее значения Глава К Разделай а алапнауй 9! для меньших аргументов. Например, в разделе 2.3.2 мы описывали время Т(п) работы процедуры Мккан-Яокт в наихудшем случае с помощью рекуррентного соотношения 9 (1), если п = 1, Т(п) = 2Т(п/2) + 9(п), если и ) 1, (4.1) В методе нодстеновки мы делаем предположение о границе, а затем исполь- зуем метод математической индукции для доказательства его корректности. В методе деревьев рекурсии рекуррентное соотношение преобразуется в де- рево, узлы которого представляют стоимости на разных уровнях рекурсии. Затем для решения рекуррентного соотношения используются методы оценки сумм.
° В основном методе (шазгег шебзод) граничные оценки рекуррентных соотношений представляются в виде Т(п) = аТ(п/о) + /(и), (4.2) где а > 1, 0 ) 1, а /(и) — заданная функция. Такие рекуррентные соотношения возникают очень часто. Рекуррентное соотношение вида (4.2) описывает алгоритм "разделяй и властвуй", который создает а подзадач, каждая из которых имеет размер, равный 1/6 размера исходной задачи, и шаги разделения и комбинирования которого в сумме занимают время Дп). Для использования основного метода вам нужно запомнить три разных случая, после чего вы сможете легко определять асимптотические границы для многих простых рекуррентных соотношений. Мы будем использовать данный метод для определения времени работы алгоритмов "разделяй и властвуй" для поиска максимального подмассива и для умножения матриц, а также для множества алгоритмов, основанных на этой парадигме, в других местах книги.
решением юторого является функция Т(п) = 9(п 1к п). Рекуррентные соотношения могут принимать множество разных форм. Например, рекурсивный алгоритм может делить задачу на подзадачи разного размера, например, разбивая на части, представляющие собой 2/3 и 1/3 исходной задачи. Если при этом разделение и комбинирование выполняются за линейное время, время работы такого алгоритма определяется рекуррентным соотношением Т(п) = Т(2п/3) + Т(п/3) + 6(п). Подзадачи не обязаны быть ограниченными некоторыми постоянными долями размера исходной задачи.
Например, рекурсивная версия линейного поиска (см. упр. 2.1.3) создает только одну подзадачу, содержащую только на один элемент меньше, чем исходная задача. Каждый рекурсивный вызов требует константного времени плюс время на рекурсивный вызов, в свою очередь осуществляемый им, что приводит к рекуррентному соотношению Т(п) = Т(п — 1) + 6(1), В этой главе предлагаются три метода решения рекуррентных соотношений, т.е. получения асимптотических границ решения "9'* или "О". ЧаСтЬ 1 Основы Иногда нам будут встречаться рекуррентные соотношения, которые представляют собой неравенства, такие как Т(и) < 2Т(п/2) + Э(п). Поскольку такие рекуррентные соотношения указывают только верхнюю границу Т(п), их решения мы будем записывать с применением О-обозначений (а не Н-обозначений).
Аналогично, если это неравенство обратить (так, что оно примет вид Т(п) > 2Т(п/2)+9(п)), то, поскольку такое рекуррентное соотношение дает толью нижнюю границу Т(п), в его решении будут использоваться П-обозначения. Технические детали рекуррентиых соотношений На практике при составлении и решении рекуррентных соотношений мы пренебрегаем рядом технических деталей. Например, если мы вызываем процедуру МЕКОЕ-ЯОКТ для нечетного юличества элементов и, то в результате мы получаем подзадачи размером (и/2) и (и/21. Ни один из этих размеров в действительности не равен и/2, поскольку и/2 не является целым числом при нечетном и. Технически рекуррентное соотношение, описывающее время работы процедуры Мексе-Яокт в наихудшем случае, в действительности равно Т(п) = если = 1, И Т((п/21) + Т(~п/21) + 9(п), если и > 1 .
Граничные условия — еще один пример технических особенностей, которые обычно игнорируются. Поскольку время работы алгоритма с входными данными фиксированного размера выражается константой, то в рекуррентных соотношениях, описывающих время работы алгоритмов, для достаточно малых и обычно справедливо соотношение Т(п) = 9(1). Поэтому для удобства граничные условия рекуррентных соотношений, как правило, опускаются и предполагается, что для малых и время работы алгоритма Т(п) является константой. Например, рекуррентное соотношение (4.1) обычно записывается как Т(п) = 2Т(н/2) + 9(п), (4.4) без явного указания значений Т(п) для малых п.
Причина состоит в том, что хотя изменение значения Т(1) и приводит к изменению решения рекуррентного соотношения, это решение обычно изменяется не более чем на постоянный множитель, так что порядок роста остается неизменным. Формулируя и решая рекуррентные соотношения, мы часто опускаем полы, потолки и граничные условия.
Мы продвигаемся вперед без этих деталей, а затем выясняем, важны они или нет. Обычно они не играют никакой роли, но мы должны знать, когда это не так. В подобных ситуациях помогают опыт, а также некоторые теоремы. В этих теоремах формулируются условия, когда упомянутые детали не влияют на асимптотическое поведение рекуррентных соотношений, возникающих в ходе анализа алгоритмов (см. теорему 4.1).
Однако в данной главе мы не будем опускать технические детали, так как это позволит продемонстрировать некоторые тонкости, присущие методам решения рекуррентных соотношений. 93 Глава 4. Разделяй и власмвуй 4,1. Задача поиска максимального подмассива Предположим, что у вас появилась возможность вложить деньги в корпорацию по производству неустойчивых химических соединений Ч01а!!1е С!зеписа! Со!рота!юп.
Подобно производимой продукции цена акций Чо!ай!е СЬеш!са! Сотротабоп тоже очень неустойчива. Вы можете купить только один комплект акций и продать его в какой-то другой день, осуществляя покупки и продажи после закрытия торгов. Ваши неудобства компенсируются тем, что вы владеете информацией о будущих ценах на акции. Ваша цель — получить максимальную прибыль. На рис.4.1 показана цена акций за 17-дневный период.
Вы можете покупать акции в любой день, начиная с нулевого дня, когда цена равна $100. Конечно, вы захотите купить подешевле, а продать подороже, но — увы! — так может и не получиться. На рис. 4.1 наименьшая цена достигается после седьмого дня, т.е. после того, как будет достигнута максимальная цена после первого дня. 120 110 100 90 80 70 60 0 ! 2 3 4 5 6 7 8 9 10 11 12 13 !4 !5 16 День 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Цена 100 113 110 85 105 102 86 63 81 101 94 106 101 79 94 90 97 Изменение 13 -3 -25 20 -3 -16 -23 18 20 -7 12 -5 -22 15 -4 7 Рнс. 4.1. Информация о цене акций Чо!ац!е Сьеппса! Созрогабоп после закрытия торгов за !7-дневный период. На горизонтальной осн днаграммы указан день торгов, на вертикальной— цена.
В нижней строке таблицы указано изменение цены по сравнению с предыдущим днем. Можно решить, что прибыль всегда можно максимизировать, либо покупая по наименьшей цене, либо продавая по наибольшей. Например, на рнс. 4.1 можно было бы максимизировать прибыль, выполняя покупку по наименьшей цене, которая достигается после торгов седьмого дня. Если бы такая стратегия всегда работала, то было бы просто определить, как максимизировать прибыль: найти наибольшую и наименьшую цены, а затем слева от наивысшей цены выполнить поиск наинизшей, а справа от наинизшей цены выполнить поиск наивысшей н взять пару с максимальным отличием.
Но иа рис. 4.2 показан контрпример, демонстрирующий, что иногда максимальная прибыль достигается и не при покупке по наинизшей цене, и не при продаже по наивысшей. Перебор Можно легко разработать решение зтой задачи, основанное на грубой силе: просто испытать все возможные пары дат покупки и продажи, в которых дата Часть 1. Основы ю 9 в 6 О 1 2 3 4 Рнс. 4.2.
Пример, демонстрирующий, что максимальная прибыль не всегда начинается с минимальной цены и не нсегда заканчиваетса максимальной. Здесь вновь на горизонтальной оси диаграммы указан день торгов, на вертикальной — цена Максимальная прибыль в $3 достигается при покупке после торгов во второй день н продаже после торгов в третий день.
Ио цена $7 во второй лень не является наинизшей, как и цена $10 в третий день не является наивмсшей. покупки предшествует дате продажи. Период из и дней имеет (") таких пар дат. Поскольку (2) представляет собой !В(пз), и лучшее, на что мы можем надеяться, — зто вычисление каждой пары за константное время, такой подход будет давать время работы П1пз). Нельзя ли достичь чего-то лучшего? Преобразование Чтобы получить алгоритм со временем работы о(пз), взглянем на входные данные под несколько иным углом. Мы хотим найти последовательность дней, для которых итоговая разница между первым и последним днем максимальна.
Вместо того чтобы работать с ежедневными ценами, давайте рассмотрим ежедневное изменение цены, где изменение в день з представляет собой разность между ценой после торгов в день 3 и ценой в день з — 1. На рис.4.1 эти изменения показаны в нижней строке. Если рассматривать эту строку как массив А, показанный на рис.4.3, то задача заключается в поиске непустого непрерывного подмассива А, значения которого имеют наибольшую сумму. Назовем такой непрерывный подмассив максимнлвнмм подмассивпм. Например, в массиве на рис.
4.3 максимальным подмассивом массива А(1 .. 1б] является А[8 .. 11) с суммой 43. Таким образом, лучше всего покупать акции непосредственно перед восьмым днем !т.е. после торгов седьмого дня), а продавать после торгов одиннадцатого дня, получая при этом прибыль в $43 с акции. На первый взгляд, такое преобразованием ничем не может нам помочь.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
