Алгоритмы - построение и анализ (1021735), страница 248
Текст из файла (страница 248)
к=о Применим этот метод, например, к ряду ~;~~ (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 ф Я. Множество не может содержать один и тот же элемент дважды', кроме того, элементы множества не упорядочены. Два множества А и В равны (что записывается как А = В), если они содержат одни и те же элементы. Например, (1,г,з) = (з,г,1).
Для часто встречающихся множеств используются специальные обозначения: 'Модификация множества, юторое может содержать несколью одинаювык элементов, называется мультимножеством (юц16аее). Приложение Б. Множества и прочие художества 1203 ° 9 обозначает пустое множество, т.е. множество, не содержащее ни одного элемента; ° Х обозначает множество целых чисел, т.е. множество (..., — 2, — 1, О, 1, 2,... ); ° К обозначает множество действительных чисел; ° 'гч обозначает множество натуральных чисел, те. множество (1, 2, 3,...)з.
Если все элементы множества А содержатся во множестве В, т.е. из х е А вытекает х Е В, то мы записываем, что А С В и говорим, что множество А является подмножествам В. Множество А является истинным подмножеством (ргорег зпЬзе1) множества В (что записывается как АСВ), если А С В, но А ф В. (Многие авторы используют обозначение А с В не только для истинных подмножеств, но и для отношения обычного подмножества.) Для любого множества А справедливо А С А; для двух множеств А и В А = В тогда и только тогда, когда А С В и В С А.
Для любых трех множеств А, В и С из А С В и В С С следует А С С. Для любого множества А справедливо соотношение 9 С А, Иногда множество определяется посредством другого множества. Так, имея множество А, мы можем определить множество В С А, указав свойство, которым обладают элементы множества В. Например, множество четных чисел можно определить следующим образом: (х: х б Е и х/2 — целое число). Двоеточие в такой записи читается как "такой что" (некоторые авторы вместо двоеточия используют вертикальную черту). Для данных двух множеств А и В можно определить новые множества при помощи следующих операций над множествамн.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
