Д. Кнут - Искусство программирования том 1 (1119450), страница 30
Текст из файла (страница 30)
распределеш»е, которому соответствует производящая функция (д — рл) ", где д = р + 1. в1.2.11. Асимптотические представления Во многих случаях для того, чтобы сравнить одну величину с другой, достаточно знать не точные, а приближенные их значения. Например, формула Стирлннга для и! — это удобное приближение подобного типа для больших и; мы пользовались также приближением И„ж !пи + у.
При выводе подобных асимпп»этических формул обычно используются методы высшей математики, но в следующих разделах для получения нужных результатов мы не будем выходить за рамки элементарной математики. э1,2.11.1. Символ О. Поль Бахман (Рап! Вас)»шапп) в книге Апа)убвсйе ЯэЫепсбеог)е (1894 г.) ввел очень удобное обозначение для использования в приближенных формулах. Это символ О, который позволяет заменить знак "-" знаком "=" и количественно выразить степень точности, например Н„=! + +О( — ). 1 э Здесь р — вероятность того, что выпаде» "орел", а д = 1 — р.— Прим.
лед. (Читается эта запись так: "Н„равно натуральному логарифму от и плюс постоянная Эйлера плюс о большое от единицы на п".) Вообще говоря, каждый раз, когда /(п) является функцией от положительного целого и, можно использовать запись 0(/(п)); она обозначает величину, точное значение которой неизвестно, и известно только, что ее значение не слишком велико*. Запись 0(/(п)) всегда обозначает следующее; существуют положительные константы М и ио, такие, что величина х„, представленная в виде О(/(п)), удовлетворяет условию (х„! < М (/(п)! для всех целых п > по. Мы не можем сказать, каковы на самом деле эти конгтанты М и ио, так как в каждом случае они зависят от соотношения, в котором использован символ О. Например, соотношение (1) означает, что (̈́— !пи — у! < М/и, когда и > по. Хотя значения констант М и ио не указаны, мы можем быть уверены, что для достаточно большого п величина 0(1/и) будет сколь утодно малой. Рассмотрим еще несколько примеров.
Мы знаем„что 1з+2з+ +из = 1п(п+ 1)(и+ 1) = 1пз+ 1из+ ~1п Отсюда гледует, что 1 +2 + +п~ =0(п~), 1 +2 + +<<~ =0(из), 1з+2 -Ь. -Ьп~ = — 'из+0(пз). (2) (3) (4) (Р(и)1 «<ао(+ (а<!и+ + !а )п™ = ((ао!/п +(ад)/и '+ .. + ! !)п» <((ао(~.(а,(+. +(а !)и-, где и > 1. Поэтому можно взять М = (ао(+ (а<(+ +(а ! и по = 1. Можно было бы взять также, скажем, М = (ао(/2 + (а,(/2 '+ + (а„,) и ио — — 2. Символ 0 очень полезен в работе с приближенными формулами, так как позволяет кратко описать суть дела, опустив ненужные детали. Более того, с символами 0 можно выполнять хорошо известные алгебраические операции, хотя нужно иметь в виду некоторые особенности. Самый важный ь<омент заключаетгя н односторонности ровеисгив: мы пишем -'и~+и = 0(и ), но ни в коем случае не 0(п~) = -'пз + п.
(В противном случае, так как -'пз = 0(п~), можно прийти к полному абсурду, получив равенство —,'пз = -'из + и.) Мы всегда следуем соглашению, что правая часть равенства несег не больше информации, чем левая; правая часть— это "огрубление" левой. Соглашение по поводу использования знака "=" можно более точно сформулировать следующим образом: формулы, содержащие запись О(/"(п)), можно рассматривать как множества функций от и. Запись 0(/(и)) обозначает множество всех е 11о ераеиееию с /(и) — ПРим ред. Соотношение (2) до«его шо грубое, хотя и правильное.
Соотношение (3) является более сильиыи, а (4) — еще сильнее. Чтобы подтвердить правильность этих соотношений, докажем, что еглп Р(п) = ао+ а<и+ + а и"'- -произвольный многочлен степени, меньшой или равной ги, то Р(п) = 0(и"'). Это вытекает из следующих оценок: функций д от целых чиселядля которых существуют константы М и по, такие, что ~д(п)( < М ~У(п)) для всех целых и > по.
Если Б и Т вЂ” множества функций, то Б+Т обозначает множество (д+ А:, ( д 6 Б и И Е Т); аналогично определяются множества 5+ с, Б — Т, Б Т, 1оя 5 и т. д. Если а(п) и Б(п) — формулы, содержащие символ О, то запись а(п) = Б(п) означает, что множество функций, относящихся к классу а(п), содержится в множестве функций, относящихся к классу Б(п). Следовательно, большинство привычных операций можно выполнять, пользуясь знаком "=': если а(п) = й(п) и Б(п) = 7(п), то а(п) = у(п).
Кроме того, если а(п) = д(п) и если Ю(п) — формула, полученная в результате подстановки Ф(п) вместо некоторых а(п) в формуле 7(п), то 7(п) = б(п). Из этих двух утвернсдений следует, например, что если д(хыхы...,х ) — любая действительная функция и если аь(п) = Бь(п) для 1 < Й < т, то д(а1(п),аг(п) о (п)) = д(А(п),дг(п), Ф„,(п)) Вот некоторые простые операции, которые можно выполнять с символом О у(п) = 0(у(п)), (5) Символ 0 также часто используется с функциями комплексного переменного х в окрестности точки х = О Через 0(у(г)) мы обозначаем любою величину д(х), такую, что (д(х)) < М~((х)) при ~х~ < г (Как и прежде, М и г — это некоторые неопределенные константы, хотя мы мыли бы определить их, если бы захотели.) Применительно к 0-записи всегда должны указываться используемая переменная и область ее изменения.
Если у нас переменная п, то неявно предполагается, что в записи 0(У(п)) подразумеваются функции от большого целого п Если же используется переменная х, то предполагается, что 0(у(х)) относится к функциям малого комплексного числа х. Предположим, что д(х) — это функция, заданная бесконечным степенным рядом д(г) = ~ ~аьх~, ь>о сходящимся в точке х = хо.
Тогда сумма абсолютных значений ) >о ~аьх" ~ сходится также при 14 < ~хо! Если хо ~ О, то можно записать д(х) =ао+агх+ +а х +0(х ~') Так как д(х) = ао+а1х+ +а х"'+с~+'(а .1+а ьзх+' ), нужно только показать, что величина в скобках ограничена при ф < г, где г — некоторое положительное число действительно, величина (а ~.1(+(а ~.з(г+(а „.з(го+ ° . является ее верхней гранью при ф < г < (хо).
с ° 0(7(п)) = 0(7(п)), если с — константа, 0(~(п)) + 0(~(п)) = 0(Дп)), о(о(х(.))) = о(х( )), 0(7(п)) 0(д(п)) = 0(у(п)д(п)), 0(у (а) д(п)) = 7(п) 0(д(п)) . (6) (7) (8) (9) (10) Рассмотрим несколько примеров. Производящие функции, приведенные в разделе 1.2.9, для всех неотрицательных целых гп дают важные асимптотические формулы для достаточно малых ж сл 1 ч т+ х2 ~ ч хгп ь 0(в~к+!) 2! т) (12) ( 1) т.~.1 1п(1+в) = в — -гт+ + в"'+0(в ~') 2 т (1+.)-=1+ .+( )" + +( ).-+0(.-+'), (14) — 1п — = г + Нзв + ..
+ Н в + 0(в~+'). 1 — г 1 — в (15) Важно отметить, что константы М и г при каждом конкретном 0 зависят одна от другой. Например, очевидно, что функция е- = 0(1) при (т! < т для любого фиксированного г, так как )е-) < е", но не существует константы М, такой, что (е*~ < М для всех х Поэтому по мере увеличения г нам придется брать все большее и большее значение М. Иногда асимптотическая формула справедлива, хотя не существует соответствующего сходящегося бесконечного ряда Например, основные формулы т п'= ~~ [ ]и' "+0(п' '), ь=о пг = ~ ~( — 1) '[ ]и" "+0(п" '), ь=в (16) (17) расходится для всех п (см.
упр. 12). Ра ~умеется, если т — неотрицательное целое, то и" и пг являются просто многочленами степени т и (17) — это, в сущности, то же, что и 1.2.6 (44) Если т — неотрицательное целое и )и! > )г(, то бесконечная сумма ~~, с~„"ьДп" "сходится к п'=1/(и — 1) — ". Эту сумму можно записать также вболее естественном виде, 2 1 (~ ')и" ", воспользовавшись соотношением 1.2.6-(58). Приведем один простой пример для иллюстрации введенных понятий. Рассмотрим величину ,"/п.
По мере увеличения п последовательность корней и-й степени из фиксированного числа будет убывать, но совсем не очевидно, убывающей или возрастающей будет последовательность ~/и Оказывается, что ~/п убывает и стремится к единице. Теперь давайте рассмотрим несколько более сложную величину п(~/й — 1). Здесь Яп — 1) убывает при увеличении п. А как будет себя вести и (~/й — 1)? Эта задача легко решается с помощью приведенных выше формул. Имеем ~/й = лы "/" = 1 + (1п и/и) + 0(()п и/п)т), (18) выражающие факториальные степени через обычные степени, асимптотически спра- ведливы для любого действительного г и любого фиксированного целого т > 6, в то время как сумма так как !пи/и -+ 0 при и -+ оо (см.
упр. 8 и 11). Соотношение (18) доказывает утверждение о том, что ~/и -у 1. Более того, из него следует, что пЯй — 1) = и(!пп/!!+ 0(()пп/п)е)) = 1пп+ 0((!пп)~/п). (19) Другими словами, п(т/и — 1) приближенно равно 1п и; эти величины отличаются на величину 0((!ил)т/и). которая стремится к нулю при п, стремящемся к бесконечности. Многие часто неправильно пользуются записями с символом О, считая, что они дают точный порядок роста, т. е.
определяют как верхнюю, так и нижнюю грани. Например, алгоритм сортировки и чисел можно назвать неэффективным. "потому что время его выполнения составляет 0(пз)". Но из этого никак не следует, что время выполнения алгоритма не составляет также 0(п). Для нижних граней существует другая запись, с символом "большая омега".
Утверждение (20) д(п) = Й(/(и)) означает, что существуют положительные константы Ь и пе, такие, что [д(п) ~ > 1 [/(и)! для всех и > пе. Эта запись позволяет сделать правильный вывод о том, что алгоритм сортировки, время выполнения которого равно П(пз), будет не таким эффективным, как алгоритм, время выполнения которого равно 0(п 1о8п) (для достаточно больших и).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
