Aszimptotikus egyenlőség

Az, hogy az ${\displaystyle f(n)}$ és a ${\displaystyle g(n)}$ sorozat aszimptotikusan egyenlő (${\displaystyle f\left({n}\right)\sim g\left({n}\right)}$) azt jelenti, hogy ${\displaystyle f\left({n}\right)/g\left({n}\right)\rightarrow 1}$, ha ${\displaystyle n\rightarrow \infty }$.

Az aszimptotikus egyenlőség csak a két függvény hányadosáról szól, semmit sem mond a két függvény különbségéről. Így az akár végtelenhez is tarthat.

Becslésre használják a matematika különböző területein.

Példák

Stirling-formula a faktoriális nagyságrendjéről:

${\displaystyle n!\sim {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}}$

A prímszámok eloszlása:

Jelölje π(x) az 1 és x közötti prímszámok számát. Ekkor:

${\displaystyle \pi (x)\sim {\frac {x}{\ln x}}}$

Az algoritmusok műveletigényét szintén szokás aszimptotikus egyenlőséggel megadni.

Továbbá alkalmazzák például a statisztikában.

Források

• Freud-Gyarmati: Számelmélet
• Algoritmusok műveletigénye^[halott link]
• Statisztikai alkalmazások