Matematiikka:Asymptoottinen kasvunopeus

Tällä käsitteellä ei ole otsikon muodostavia nimityksiä.

o-notaatio (luo nimityssivu)

Määritelmä Käsite, jonka avulla voidaan verrata esimerkiksi lukujonojen tai funktioiden kasvunopeuksia ja jakaa esimerkiksi lukujonoja tai funktioita erilaisiin luokkiin niiden kasvunopeuden perusteella

Selite

Asymptoottisen kasvunopeuden käsite ja siihen liittyvä $O$-notaatio on hyödyllinen etenkin analysoitaessa algoritmien tehokkuutta.

Se voidaan määritellä funktioille seuraavasti, ja aivan vastaavalla tavalla esimerkiksi lukusarjoille.

Olkoot $f:\mathbb{ℝ}\to \mathbb{ℝ}$ ja $g:\mathbb{ℝ}\to \mathbb{ℝ}$ funktioita. Jos on olemassa sellaiset vakiot $x_0,M\in \mathbb{ℝ}$, että $|f(x)|\le M|g(x)|$, kun $x\ge x_0$, sanotaan, että funktiolla $f$ on sama asymptoottinen kasvunopeus kuin funktiolla $g$ tai että $f$ kasvaa korkeintaan yhtä nopeasti kuin $g$. Tätä merkitään $O$-notaatiolla: $f(x)=O(g(x))$.

Esimerkiksi jos $f(x)=6x^4-2x^3+5$, niin $f(x)=O(x^4)$. Jos nimittäin $x\ge 1$, pätee \begin{equationarray} \vert 6x^4-2x^3+5 \vert &\le& 6x^4+\vert2x^3\vert+5 \\ &\le&6n^4+2n^4+5n^4\\ &=&13x^4.\end{equationarray}

Vastaavasti käytetään pikku-o-notaatiota, eli merkintää $f(x)=o(g(x))$ kuvastamaan sitä, että funtio $g(x)$ kasvaa huomattavasti nopeammin kuin funktio $f(x)$. Täsmällinen määritelmä on, että jokaista reaalilukua $ϵ>0$ kohti löytyy sellainen $x_{ϵ}\in \mathbb{ℝ}$, että $|f(x)|\le |ϵg(x)|$, kun $x\ge x_{ϵ}$.
br/> Esimerkiksi $2x=o(x^2)$, sillä jos $ϵ>0$, niin $2x\le ϵx^2$, kun $x\ge \frac{2}{ϵ}$ (viimeiset kaksi epäyhtälöä ovat itse asiassa [[Matematiikka:ekvivalenssi

|ekvivalentit]], kun $x>0$m mikä huomataan jakamalla ensimmäinen epäyhtälö puolittain luvulla $ϵx$), eli voidaan valita $x_{ϵ}=\frac{2}{ϵ}.$

Jos $f(x)=o(g(x))$, siitä seuraa aina, että $f(x)=O(g(x))$. Käänteinen ei kuitenkaan päde. Esimerkiksi $2x^2=O(x^2)$ (sillä $|2x^2|\le 2|x^2|$ kaikilla $x\in \mathbb{ℝ}$), mutta $2x^2\ne o(x^2)$, koska silloin, kun $ϵ<2$, ei millään luvulla $x$ päde, että $2x^2\le ϵx^2$.

Jos $(a_n)=O(b_n)$ ja $(b_n)=O(a_n)$, jonot $(a_n)$ ja $(b_n)$ kasvavat yhtä nopeasti. Tällöin merkitään $(a_n)=\mathrm{\Theta }(b_n)$.

> Luokat $O$, $o$ ja $\mathrm{\Theta }$ voidaan määritellä yhtäpitävästi myös tutkimalla lausekkeen $\frac{|f(x)|}{|g(x)|}$ arvoa, kun $x$ lähenee ääretöntä. Jos ${\displaystyle }$\textrm{lim sup}_{x \to \infty} \frac{\vert f(x) \vert}{\vert g(x) \vert} < \infty,${\displaystyle }$ niin $f(x)=O(g(x))$. Jos taas ${\displaystyle }$\textrm{lim sup}_{x \to \infty} \frac{\vert f(x) \vert}{\vert g(x) \vert} < \infty,${\displaystyle }$ niin, $f(x)=o(g(x))$. Jos puolestaan on olemassa sellaiset positiiviset vakiot $c,C$, että Jäsentäminen epäonnistui (Jäsennysvirhe): {\displaystyle c \lt \frac{\vert f(x)\vert}{\vert g(x) \vert} \lt C} , niin $f(x)=\mathrm{\Theta }(g(x))$.

Erikieliset vastineet

asymptotic growth rate (luo nimityssivu)	englanti (English)
o-notation (luo nimityssivu)	englanti (English)

Alaviitteet

Lähdeviittaus tähän sivuun:
Tieteen termipankki 6.12.2025: Matematiikka:Asymptoottinen kasvunopeus. (Tarkka osoite: https://tieteentermipankki.fi/wiki/Matematiikka:Asymptoottinen kasvunopeus.)

Siirry tarkastelemaan sivun muokkaushistoriaa →