Асимптотический анализ

---

Например, в функции ${\displaystyle f(n)=n^{2}+3n}$ при стремлении ${\displaystyle n}$ к бесконечности слагаемое ${\displaystyle 3n}$ становится пренебрежимо малым по сравнению с ${\displaystyle n^{2}}$, поэтому про функцию ${\displaystyle f(n)}$ говорят, что она «асимптотически эквивалентна ${\displaystyle n^{2}}$ при ${\displaystyle n\to \infty }$», что зачастую также записывают как ${\displaystyle f(n)\sim n^{2}}$. Примером важного асимптотического результата является теорема о распределении простых чисел. Пусть ${\displaystyle \pi (x)}$ обозначает функцию распределения простых чисел, то есть, ${\displaystyle \pi (x)}$ равна количеству простых чисел, которые меньше либо равны ${\displaystyle x}$, тогда теорема может быть сформулирована как ${\displaystyle \pi (x)\sim {\frac {x}{\log x}}}$.

Пусть ${\displaystyle f(x)}$ и ${\displaystyle g(x)}$ — некоторые функции. Тогда бинарное отношение ${\displaystyle \sim }$ определяется таким образом, что

---