Асимптотическая эквивалентность

Как в учебнике

При $g(n)>0$ для достаточно больших натуральных $n$ асимптотическая эквивалентность $f(n)\sim g(n)$ означает $\lim_{n\to\infty}f(n)/g(n)=1$. Предполагается также, что функция $f$ положительна начиная с некоторого входа. Эквивалентно, $(f(n)-g(n))/g(n)\to0$.

Для $f(n)=n+7$ и $g(n)=n$ отношение равно $1+7/n$, поэтому $n+7\sim n$. Абсолютная разность всё время равна 7, но относительно растущего масштаба она исчезает. Равенства значений при конечных $n$ не требуется.

Функция $3n+7$ не эквивалентна $n$: отношение стремится к 3. Обе имеют порядок $\Theta(n)$, поэтому асимптотическая эквивалентность строже совпадения порядка. Постоянный множитель здесь существенен.

Эта запись отличается от $X\sim D$ в вероятности, где тот же знак сообщает распределение случайной величины. Автоматическая подстановка эквивалентных функций в разность близких величин может дать ошибку: главные части могут сократиться, после чего отброшенная разность определяет результат.

Определение задаёт проверку для любого относительного допуска $\varepsilon>0$: начиная с некоторого $n_0$ должно выполняться $|f(n)/g(n)-1|<\varepsilon$. Порог разрешено выбирать в зависимости от допуска. Для $f(n)=n+7$ достаточно $n>7/\varepsilon$. Поэтому несколько близких отношений ещё не доказывают эквивалентность: необходим контроль всего дальнейшего хвоста при каждом, сколь угодно малом, положительном допуске.

Определения и обозначения: Mathematics for Computer Science.

Связанные понятия: Предел последовательности, Θ-большое: точный порядок роста.