Допустим, нам нужно приближённо оценить какую-то величину. Мы можем просто записать знак $\approx$.

Поль Бахман в книге Analytische Zahlentheorie (1894) ввёл очень удобное обозначение $O$, которое позволило заменить знак $\approx$ на знак $=$ и количественно выразить точность оценки.

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

Сейчас мы имеем аж целых $5$ символов для работы. Называются эти символы символами Ландау, в честь Эдмурда Ландау, который ввёл два символа $O$ и $o$ 1909 году. Позже математическое сообщество расширило обозначения, добавив $\Omega$, $\omega$ и $\Theta$, а благодаря Дональду Кнуту обозначения $\Theta$ и $\Omega$ добрались и до информатиков.

Функция принадлежит своему $O$-большому. Также работает для остальных символов, кроме $o$-малого.

Константы, как внутренние, так и внешние, не влияют на класс. Работает для всех символов.

При сложении результат не выходит из класса. Также работает для $\Theta$ и $o$, но не работает для $\Omega$.

Операция взятия $O$-большого идемпотентна. Аналогично для остальных.

Функции-множители можно безболезненно вносить и выносить из знака $O$-большого, $o$-малого, $\Theta$, но не всегда из $\Omega$.

Как следствие, любой класс выразим через $O(1)$.

Операция взятия $O$-большого транзитивна. Выполняется и для остальных, но для $\Omega$ зависит от знака.

Из асимптотической формулы не следует сходимость (ряда или интеграла).

Например, асимптотические формулы, выражающие восходящую и нисходящую степени числа $n$

Обе асимптотические формулы верны для любого действительного $r$ и любого фиксированного целого $m > 0$. Однако, сумма

расходится для всех $n$ несмотря на то, что $n^{1/2-m-1} \to 0$ при $m \to \oo$.

Так что нельзя путать аппроксимацию с пределом. Асимптотический ряд — это не бесконечная сумма, стремящаяся к точному значению, а последовательность всё более точных приближений.

Символы Ландау можно использовать также и для вывода каких-то соотношений. Например, используя формулу Тейлора для $e^x$, можем провести следующие интересные манипуляции

Формулу Тейлора мы имели право применить потому что $\ln n / n \to 0$ при $n \to \oo$.

Из этого равенства можно вывести, например, что $n \cdot \bigl( \sqrt[n]{n} - 1 \bigr) \approx \ln n$:

Здесь выполняется транзитивность, а значит мы можем расставить множество функций по порядку их роста. Например:

Это очень помогает нам при подсчёте пределов, так как эквивалентные функции можно заменять друг на друга без потери точности.

Таковыми являются, например, $sin(x)$ и $x$ при очень маленьких $x$.

Когда мы решаем какую-то задачу, мы хотим оценить, какое решение и когда будет самым лучшим. Для этого нам надо знать, сколько по времени будет работать программа и сколько оперативной памяти она займёт (меньше — лучше). Брать в руки секундомер и лупу, чтобы смотреть внутрь компьютера при каждом запуске идея конечно хорошая, но не эффективная. В ней мы напрямую зависим от мощности процессора, памяти, погодных условий, количества человек в комнате, количества пылинок в системе охлаждения — не очень круто.

Намного лучше мы поступим, если посмотрим на код программы и посчитаем, сколько раз будет выполняться основная операция (В сортировках — сравнения, в вычислениях — арифметические операции и т.д.). Но тут можно сильно закопаться, так как зачастую количество сильно зависит от входных данных, а они бывают очень разными. Тогда придётся смотреть на их распределение, находить самый лучший случай, самый худший, средний, отклонение от среднего. Это полезно и даже необходимо, когда нам нужно сравнить два алгоритма примерно одинаковой сложности, но не всегда нужно и не всегда стоит затраченных усилий.

Тут нам на выручку приходят символы Ландау. Они дают понимание того, как алгоритм поведёт себя при росте размерности данных и позволяют описывать алгоритм не в терминах точного количества операций, а в терминах класса роста этого количества.

Допустим нам нужно посчитать какой-то интеграл, но функция внутри нам очень очень не нравится. Мы можем ассимптотически свести к чему-то попроще и посчитать с какой-то точностью.

А что, если нам известна только асимтотическая оценка функции на бесконечности? Можем асимптотически оценить её интеграл.

Например для $f(x) = \sqrt{x} + 1/x = O\left(x^{1/2}\right)$ будем иметь $\int\limits_0^x f(t) \, dt = O\left(x^{3/2}\right)$

Бывают также и ситуации, когда мы хотим уточнить асимптотику сходящегося интеграла или оценить сумму ряда. Для такого существуют асимптотические выражения, позволяющие перейти от суммы к интегралу и от интеграла к сумме.

Например, пусть

тогда

Или другой пример, который был упомянут в самом начале.

Пусть

Тогда

В анализе асимптотики многих алгоритмов возникают реккурентные соотношения. Например, в бинарном поиске на отсортированном массиве общее время работы будет зависеть от времени работы поиска в половине массива $T(n) = T(n/2) + O(1)$, которое, в свою очередь, будет зависеть от времени работы в четверти массива и так далее. Чтобы выяснить, какую асимптотику имеет время работы такого алгоритма, нам нужно уметь решать реккурентные соотношения.

Одним из самых крутых, методов получение приближённых значений сумм является метод суммирования Эйлера. Идея метода — аппроксимировать сумму интегралом.

Вот пусть нам надо найти значение суммы $\sum\limits_{k=1}^{n-1} f(k)$. Попытаемся аппроксимировать эту сумму интегралом $\int\limits_1^n f(x) \, dx$.

Сложим это равенство при всех $k$ от $1$ до $n-1$. Получим

Теперь мы можем выразить сумму

где $B_1(y)$ — многочлен $B_1(y) = y - 1/2$. В обозначениях спойлер: тут появятся многочлены Бернулли.

Продолжая интегрировать по частям мы будем получать всё более и более точные формулы.

Посмотрим на многочлены Бернулли. Вспомним рекуррентное дифференциальное соотношение

Используя это свойство получим полезную формулу для того оценочного интеграла, проинтегрировав по частям

Используя эту формулу мы можем улучшить оценку суммы, и делать это до такого порядка, до какого захотим.

где $R_{m,~ n}$ — остаточный член, представимый как поправка

Этот остаточный член мал при очень маленьких значениях $B_m (x \bmod 1) \, f^{(m)} (x) / m!$. Фактически, для чётного $m$

К сожалению, часто бывает, что при увеличении $m$ функция $f^{(m)} (x)$ возрастает по модулю. Существует «наилучшее» значение $m$, при котором $|R_{m,~ n}|$ минимален, то есть такое $m$, при котором неприятный остаточный член вносит минимум путаниц в формулу суммы. Оценивать остаток можно следующим методом:

При чётном $m$ и при условии, что $f^{(m)} (x)$ имеет постоянный знак для всех $1 < x < n$, значение остаточного члена по модулю не превосходит значения последнего вычисленного члена, то есть

Существует и более мощное утверждение, накладывающее не такие сильные ограничения на функцию. При чётном $m$ и при условии, что $f^{(m+2)} (x) \, f^{(m+4)} (x) > 0$ для всех $1 < x < n$, существует такая константа $0 < \theta < 1$, что

Тогда получаем

Получение формулы Стирлинга

Применим метод суммирования Эйлера для получение приближённой формулы Стирлинга. Пусть $f(x) = \ln x$. Применим формулу суммирования Эйлера, получим

Обратите внимание: мы аппроксимировали сумму $\sum\limits_{k=1}^{n-1} \ln k = \ln~ (n-1)!$ интегралом $\int\limits_1^n \ln x \, dx = n \ln n - n + 1$.

Раскрывая скобки в сумме получаем, два ряда, один из которых сходится к какой-то константе $\sigma$:

Подставив этот результат в исходную формулу, получим логарифм формулы Стирлинга

Потенцируя, и используя то, что $e^\sigma = \sqrt{2\pi}$, получаем формулу Стирлинга

Обрубив ряд где нам нужно и разложив экспоненту в ряд, мы сможем добиться любой желаемой точности.

Исследуем следующие суммы

Начнём с важной связи между $Q(n)$ и $R(n)$

Вспомним формулу Тейлора с остаточным членом в интегральной форме

Посмотрим на неполную гамма-функцию и её свойства, связанные с $P(n)$, $Q(n)$ и $R(n)$. Напомню, что неполная гамма-функция это

Мы будем часто использовать то, что $\gamma(a, \oo) = \Gamma(a)$.

Для неполной гамма-функции существует два полезных разложения в ряд по степеням $x$

Из второй формулы видна связь с $R(n)$:

Данное равенство специально было записано в более сложном виде, чем это необходимо, так как неполная гамма-функция $\gamma(n, n)$ является частью полной гамма-функции $\gamma(n, \oo) = \Gamma(n) = (n-1)!$, а $n! \, e^n / n^n$ — величина $R(n) + Q(n)$.

Получается, задача анализа сумм $P(n)$, $Q(n)$ и $R(n)$ сводится к нахождению хороших оценок для $\gamma(n, n)/(n-1)!$.

Определим приближённое значение $\gamma(x+1, x+y)/\Gamma(x+1)$ для фиксированного $y$ и больших $x$. По определению имеем

Оценим оба интеграла.

Начнём с первого. Выполним замену $t = (1+x) \, u$, тогда пределы интегрирования станут $[0, +\oo)$