так как Inn/n О при гг оо (см. упр. 8 и 11). Соотношение (18) доказывает утверждение о том, что 1. Более того, из него следует, что

п( - 1) = n(ln n/h + 0{{\nn/nf)) = In n + О ((In nf/n). (19)

Другими словами, - 1) приближенно равно Inn; эти величины отличаются на

величину 0((lnn)7n), которая стремится к нулю при п, стремящемся к бесконечности.

Многие часто неправильно пользуются записями с символом О, считая, что они дают точный порядок роста, т. е. определяют как верхнюю, так и нижнюю грани. Например, алгоритм сортировки п чисел можно назвать неэффективным, "потому что время его выполнения составляет 0{пУ. Но из этого никак не следует, что время выполнения алгоритма не составляет также 0(п). Для нижних граней существует другая запись, с символом "большая омега". Утверждение

з(п) = П(/(п)) (20)

означает, что существуют положительные константы L и по, такие, что

д{п) > L f{n) для всех п > пц.

Эта запись позволяет сделать правильный вывод о том, что алгоритм сортировки, время выполнения которого равно (п), будет не таким эффективным, как алгоритм, время выполнения которого равно 0(п logп) (для достаточно больших п). Но, не зная констант, подразумеваемых записями с символами О и О., мы ничего не можем сказать о том, насколько большим должно быть п, чтобы метод 0(п log п) начал выигрывать в эффективности.

И наконец, чтобы точно указать порядок роста, не давая при этом точных значений констант, можно воспользоваться записью с символом "большая тета":

З(п) = 0(/(п)) g{n)=0{f{n))Hg{n) = n{f{n)). (21)

УПРАЖНЕНИЯ

1. [НМ01] Чему равен Iim„-ooCl(n")?

► 2. [М10] М-р Далл*, применяя "очевидную" формулу 0{f{n)) - 0{f{n)) = О, получил удивительные результаты. В чем была его ошибка, и как должна выглядеть правая часть "очевидной" формулы?

3. [М15] Умножьте (In тг4-7+0(1/")) на (тг4-0(\/п)) и представьте результат с помощью символа О.

► 4. [Ml5] Дайте асимптотическое разложение п{- 1), где а > О, с точностью до членов порядка 0(1/п).

5. [М20] Докажите или опровергните следующее- 0(/(тг) 4-5(n)) =/(тг) 4-0(5(тг)), если f{n) и д{п) положительны для всех п. (Ср. с формулой (10).)

► 6. [М20] Где ошибка в следующем рассуждении? "Так как п = 0{п) и 2тг = 0(гг), ..., то

кп = 0{п) =0(гг)"

* В оригинале - В. С. Dull. От англ. "dull" ("тупица"). - Прим. перев.

7. [НМ15] Докажите, что для произвольного целого тп нельзя найти такое М, чтобы для сколь угодно больших значений х выполнялось неравенство е < Мх"*.

8. [НМ20] Докажите, что {1ап)/п О при п оо.

9. [НМ20] Покажите, что е"" = 1 + 0{z) для всех фиксированных m > 0.

10. [НМ22] Сформулируйте утверждение, аналогичное утверждению из упр. 9, относительно \n{l + 0{z")).

► 11. [МП] Объясните, почему верна формула (18).

12. [НМ25] Докажите, что [j/V-J""* ™ стремится к нулю при к оо для любого целого п. Воспользуйтесь тем, что [i/j-j,] = (-5)" [•*] (•«7(е - 1))-

► 13. [МЮ] Докажите или опровергните следующее: д{п) = П(/(п)) тогда и только тогда, когда /(п) = 0(д{п)).

*1.2.11.2. Формула суммирования Эйлера. Одним из лучших методов получения приближенных значений сумм является метод, предложенный Леонардом

Эйлером. Он состоит в том, чтобы аппроксимировать конечную сумму интегралом, и во многих случаях позволяет получать приближения с любой степенью точности. [Commentarii Academiae Scientiarum Petropolitanee 6 (1732), 68-97.]

1 2 3 4 5 6 7 Рис. 12. Сравнение суммы с интегралом.

На рис. 12 сравниваются f{x)dx и J3!t=i "Р* n = 7. Предполагая, что fix)-дифференцируемая функция, с помощью метода Эйлера можно получить удобную формулу для разности между интегралом и суммой.

Для удобства введем следующее обозначение:

{х} = xmod 1 = X - [xJ. (1)

Наадем выкладки со следующего тождества:

1"({} - I)/(х)dx = ix-k- i)/(x) 1+ - I fix)dx

= i(/(fc + l)+/(fc))-"/(x)dx. (2)

(Мы применили формулу интегрирования по частям.) Складывая обе части этого равенства для 1 < А; < п, находим, что

Г({х}-)/(х)йх= Y + Г/(х)х,

•1 1<<п -1

т. е.

Y,f{k)=l f{x)dx~\{f{n)-f{l))+ Г Bi{{x})nx)dx, (3)

где В\{х) - многочлен Bi{x) = х - \. Это и есть искомая формула, связывающая сумму с интегралом.

Продолжая интегрировать по частям, можно получать более точные приближения. Но прежде чем это сделать, рассмотрим числа Бернулли, которые являются коэффициентами следующего бесконечного ряда:

fc>0

Коэффициенты этого ряда, которые встречаются во многих задачах, были введены Якобом Бернулли (Jacques Bernoulli) в работе Ars Conjectandi, опубликованной после его смерти в 1713 году. Самое интересное, что почти в то же самое время данные числа были открыты и японцем Такакузу Секи (Takakazu Seki) и впервые опубликованы в 1712 году, вскоре после его смерти. [См. Takakazu Sekis Collected Works (Osaka, 1974), 39-42.] Имеем

Bo = l, Bi = -l, B2-i Вз = 0, 4 = -; (5)

некоторые последующие значения чисел Бернулли приведены в приложении А. Так как функция

2 2 2 е--1 2 + 1 - 1 2 ~ 2 - 1 ~ ~2 е" - 1

является четной, то

Вз = Яз = Вт = Вэ = • • • = 0. (6)

Умножая обе части равенства (4) на - 1 и приравнивая коэффициенты при одинаковых степенях 2, получим формулу

Е()в. = В„ + <5„1. (7)

(См. упр. 1.) Теперь определим многочлен Бернулли

Вт{х)=£[)в,х"-. (8)

Если m = 1, то Bi(x) = Bqx + Bi = х - ; этот многочлен использовался выше, в соотношении (3). Если m > 1, то согласно (7) Вт{1) = Вт = Вт{0); другими словами, Вт{{х}) не имеет разрывов при целых значениях х.

Вскоре станет ясно, какое отношение к нашей теме имеют многочлены Бернулли и числа Бернулли. Дифференцируя (8), находим

Bmix)=Z{l)im-k)B,x--

= тВт-Лх) (9)