Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 248
Текст из файла (страница 248)
* А.1-4. Покажите, что ~~~ о (Й вЂ” 1) /2" = О. *А.1-5. Вычислите сумму 2 ~~, 1(27с+ 1) х~~. А.1-6. Используя свойство линейности суммирования, докажите, что ,'~ О(/ь(п)) = 0(~~> /ь(п)) . А.1-7. Вычислите произведение Пь 12. 4". * А.1-8. Вычислите произведение Пь з (1 — 1/Й ). А,2 Оценки сумм Имеется множество методов оценки величин сумм, которые описывают время работы того или иного алгоритма.
Здесь мы рассмотрим толью наиболее распространенные из них. 1196 Часть Ч!П. Приложения: математические основы Математическая индукция Основным путем для вычисления сумм рядов является метод математической индукции. В качестве примера докажем, что сумма арифметической прогрессии 2 "„, к равна п (и + 1)/2. Можно легко убедиться, что эта формула верна для и = = 1.
Сделаем предположение, что эта формула верна для некоторого и и докажем, что в этом случае она верна и для п + 1: ьЧ-1 и 1 1 ~~> Й = ~> )с+ (и+1) = — п(и+ 1) + (и+1) = — (и+1) (и+ 2). а=1 ь=з Математическая индукция может использоваться не толью для точных значений сумм, но и для того, чтобы показать корректность оценок. В качестве примера рассмотрим доказательство того, что сумма геометрической прогрессии 2 "„о Зь равна 0(З"). Точнее, докажем, что 2 ь 3" < сЗ" для некоторой константы с.
При и = О формула имеет вид 2 ь р 3" = 1 < с 1, что справедливо при с > 1. о Полагая, что граница верна для и, докажем ее справедливость для и+ 1. Имеем: и+1 и г1 Е 3" = ~~~ 3" + 3"+ < сЗ" + 3"+~ = — + — сЗ"+ < сЗ"+ 1,3 с) ь=о а=о что справедливо прн (1/3 + 1/с) < 1 или, что то же самое, при с > 3/2. Таким образом, ~ ,", 3" = 0 (3"), что и требовалось показать. При использовании асимптотических обозначений для доказательства по индукции следует быть предельно внимательным и осторожным. Рассмотрим следуюшее "доказательство" того, что 2',,",, к = 0 (и). Очевидно, что 2 „', )с = 0(1).
Исходя нз справедливости оценки для п, докажем ее для и+ 1: в+1 и ,'~ к=~~ )с+(и+1) = "0(п)+0(п+1) =0(п+1). ь=1 ь=1 Ошибка в том, что "константа", скрытая в 0(п), растет вместе с и, а значит, константой не является. Мы не смогли показать, что одна и та же константа работает для всех и. Почленное сравнение Иногда можно получить неплохую верхнюю оценку ряда, заменив каждый его член ббльшим (иногда для этого можно воспользоваться наибольшим членом). Например, вот как можно оценить верхнюю границу арифметической прогрессии (А.1): ь ь 2 Приложение А. Ряды 1197 В общем случае аь < пат Е а=1 где аы,, = шахз<ь<„аь.
Если ряд в действительности может быть ограничен геометрической прогрессией, можно получить более точную оценку его суммы. Итак, пусть ряд 2 ~", о аь обладает тем свойством, что для всех й > О аь+з/аь < т, где О < т < 1 — неюторая константа. В таком случае, т.к. аь < аот, сумма ряда ограничивается сверху ь суммой бесконечной геометрической прогрессии: ~~> аь < ,'~ аот~ =ао~~ т~ =— 1 — т к=о к=О.
к=о Применим этот метод, например, к ряду ~;~~ (1с/3"). Для того чтобы сумма начиналась с Iс = О, пеРепишем РЯд как 2„"~ь о ((/с+ 1)/3"+з). ПеРвый член ао этого ряда равен 1/3, а отношение соседних членов ряда т для всех lс ) О равно (к+ 2)/3"+з 1 й+ 2 2 (/с+ 1)/3"+' 3 й+ 1 3 Таким образом, мы получаем следующую оценку: й 1+1 1 1 Š— =Š— -'- 3" 3"+з 3 1 — 2/3 — к=о Распространенной ошибкой при использовании этого метода является выяснение того, что отношение двух последовательных членов ряда меньше 1 и на этом основании делается вывод об ограниченности ряда геометричесюй прогрессией. В качестве контрпримера можно привести гармонический ряд, который расходится, так как „'~ — = 1пп ,'~ — = 1!т 9(1бп) = оо.
1 . 1 а=1 к=1 Несмотря на то, что отношение (/с + 1)-го и 1с-го членов этого ряда равно 7с/(1с + 1) < 1, ряд расходится. Для того чтобы ряд был ограничен геометричесюй прогрессией, надо показать наличие константы т < 1, такой что отношение двух соседних членов никогда не превосходит значения т. В гармоническом ряде таюй константы не существует, поскольку отношение двух соседних членов может быть сколь угодно близким к 1.
1198 Часть Ч111. Приложения: математические основы Разбиение рядов Еще один способ получения оценки сложной суммы состоит в представлении ряда как суммы двух или большего числа рядов путем разделения на части всего диапазона индексов, и оценке сумм частей по отдельности. Предположим, например, что мы ищем нижнюю границу арифметической прогрессии 2 „", /а, для которой, как мы уже выяснили, верхняя граница равна О (т12). Можно попытаться ограничить каждый член суммы наименьшим, но поскольку наименьший член этого ряда — 1, мы получим в качестве нижней границы т1, что слишком далеко от найденной верхней границы. Лучший результат для нижней границы можно получить, если сначала разбить ряд на две части.
Предположим для удобства, что и — четное число. Тогда и и/2 и и/2 ~~1 /с = ~1 й+ ,'1 й > ,'1 1О+ ~~1 (т1/2) = (т1/2) = П (пг), в=и/2+1 1=1 а=и/2+1 что является асимптотически точной оценкой, поскольку 2 ь 1/с = О (пг). В рядах, рассматриваемых при анализе алгоритмов, зачастую можно разбить ряд на части и просто проигнорировать некоторое юнечное число начальных членов.
Обычно этот метод применим, если каждый член аь ряда 2 ~ оаь не зависит от т1. Тогда для любой константы /ао > О можно записать йа-1 ав = ,'1 аа+ ~~1 аь = Е1(1)+ ~~1 ав, посюльку начальные члены суммы — постоянные величины, и в отдельный ряд выделено постоянное их юличество. После таюго разделения для поиска границ ряда ~;~", ь, аь можно использовать другие методы. Описанная методика применима и к бесконечным рядам.
Например, 'для поиска асимптотической верхней границы ряда аа /2 Е— я=о заметим, что отношение последовательных членов ряда (й+ 1)~/2~~~ (/с+ 1) 8 /сг/21 21аг 9' при /с > 3. Таким образом, можно оценить сумму исходного ряда следующим образом: /аг 2 /,г аа Ьг 2 Ьг 9 а /8 ~1 — „+",~ „<~1' „+ 2 ~ ) — О(1), в=о в=о ь=з я=о в=о Приложение А.
Ряды 1199 поскольку количество членов первой суммы — юнстанта, а вторая представляет собой бесконечно убывающую геометрическую прогрессию. Метод разбиения ряда может быть применен для определения асимптотических границ в гораздо более сложных ситуациях. Например, таким способом мы можем получить границу О (1я и) гармонического ряда (А.7): и Нп=~ к а=1 Идея заключается в разбиении диапазона от 1 до и на ~1К и) + 1 частей, с ограничением каждой части единицей. Каждая часть состоит нз членов, начинающихся от 1/2' и заканчивающихся членом 1/2'+1 (исключая сам этот член), что дает нам 1!я п1' ьч — 1 11я п1 ,'~ —,. = ~~1 1 < 1яи+ 1.
(А.10) 1 =о 1=о =о п 11яп! з*' — 1 =о з=о Приближение интегралами Если сумма может быть выражена как ~„~", / (й), где / (/с) — монотонно возрастающая функция, мы можем оценить значение ряда при помощи интегралов: и и и+1 и ~~~1:пп~~ а ~ п1-1 та (А.11) и+1 и и пи ~Е~(п~~ пи.. 1Л (А.12) Приближение интегралами (А.12) дает нам точную асимптотическую оценку и-го гармонического числа. Нижнюю границу мы получаем следующим образом: 1п+1 ~~1 — > ~ — = 1п(и+1). Й ~ х ь 1 1 (А.13) Пояснение таюй оценки показано на рис. А.1. На рисунке в прямоугольниках показаны их площади, а общая площадь прямоугольников представляет значение суммы.
Значение интеграла равно заштрихованной площади под кривой. На рис. А.1а показано, что )" 1/(7с) < ~',~ /(й), а на рис. А.16 — что 2, /(Й) < ) У(х)1(х. й=пь Если функция Х (й) монотонно убывающая, то аналогично можно показать, Приложение А. Ряды 1201 Упражнения А.2-1. Покажите, что сумма ~;,", 1//сз ограничена сверху константой. А.2-2.
Найдите асимптотическую верхнюю границу суммы 2;„ао ~п/2~1. А.2-3. Применяя разбиение ряда, покажите, что и-я частичная сумма гармонического ряда есть Й (1я и). А.2-4. Найдите приближенное значение ~;~", кз при помощи интегралов. А.2-5. Почему мы не можем применить интегральное приближение (А.12) для поиска верхней границы и-го гармонического числа непосредственно к сумме 2 ь, 1/й? Задачи А-1. Оценки сумм Дайте асимптотически точные оценки приведенных ниже сумм. Считаем, что т > О и з > Π— константы. а) 2 Й'.
я=1 б) 2 1к' 11:. я=а в) Е В" 18'Е Заключительные замечания Книга Кнута (Кпщп) !182] — отличное справочное пособие по изложенному здесь материалу. Основные свойства рядов можно найти во множестве книг, например, в книге Апостола (Арозщ!) 118] или Томаса (ТЬощаз) и Финни (Г1ппеу) [296]. ПРИЛОЖЕНИЕ Б Множества и прочие художества Во многих главах книги нам приходится сталкиваться с элементами дискретной математики.
Здесь вы более подробно ознакомитесь с обозначениями, определениями и элементарными свойствами множеств, отношений, функций, графов и деревьев. Читатели, знакомые с этим материалом, могут пропустить данное приложение. Б.1 Множества Множество (зе~) представляет собой набор различимых объектов, которые называются членами или злемежваами.
Если объект х является членом множества Я, мы записываем это как х е 5 (читается "х принадлежит Я"). Если х не принадлежит Я, мы записываем х ф Я. Множество можно описать путем явного перечисления его элементов в виде списка, заключенного в фигурные скобки. Например, мы можем определить множество Я как содержащее числа 1, 2 и 3, и только их, записав Я = (1,2, 3). Поскольку 2 является элементом множества Я, мы можем записать г Е Я, а так как 4 не является элементом Я, верна запись 4 ф Я.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
