Estimarea asimptotică

Când două secvențe sunt ambele infinitezimale sau ambele infinite, este util să puteți stabili o comparație între ele pentru a înțelege care dintre cele două tinde mai repede la 0 sau la infinit. Acest articol se referă la studiul estimărilor asimptotice pentru succesiune. Operații analoge se pot face pentru funcțiile reale ale unei variabile reale , unde în loc de infinit poate exista orice punct de acumulare comun celor două funcții.

Ordinele infinitului

O functie $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ spune infinit în $x_{0}$ ${\ displaystyle x_ {0}}$ $x_0$ dacă limita sa este infinită față de tendința de $X$ ${\ displaystyle x}$ $X$ la $x_{0}$ ${\ displaystyle x_ {0}}$ $x_0$ . În simboluri, dacă

\lim _{x\to x_{0}}|f(x)|=+\infty

{\ displaystyle \ lim _ {x \ to x_ {0}} | f (x) | = + \ infty}

\ lim _ {{x \ to x_ {0}}} | f (x) | = + \ infty

De exemplu ${\frac {1}{x}}$ ${\ displaystyle {\ frac {1} {x}}}$ ${\ frac {1} {x}}$ este infinit în $0$ ${\ displaystyle 0}$ ${\ displaystyle 0}$ Și $-e^{-x}$ ${\ displaystyle -e ^ {- x}}$ $-e ^ {{- x}}$ este infinit în $-\infty$ ${\ displaystyle - \ infty}$ $- \ infty$ .

O secvență (care poate fi considerată o funcție definită în numere naturale) se spune că este infinită dacă limita sa este infinită atunci când se tinde la $n$ ${\ displaystyle n}$ $n$ la nesfârșit. În simboluri: dacă $\{a_{n}\}$ ${\ displaystyle \ {a_ {n} \}}$ $\ {a_n \}$ este o succesiune de numere reale, $\lim _{n\to \infty }|a_{n}|=+\infty$ ${\ displaystyle \ lim _ {n \ to \ infty} | a_ {n} | = + \ infty}$ $\ lim _ {{n \ to \ infty}} | a_ {n} | = + \ infty$ . Cu toate acestea, nu toate infinitele sunt identice între ele: există de fapt o ordine în interiorul infinitelor, care depinde de tipul de curs al funcției la infinit. Iată câteva tipuri de infinit plasate în ordine crescătoare: $la$ ${\ displaystyle a}$ $la$ , $b$ ${\ displaystyle b}$ $b$ Și $c$ ${\ displaystyle c}$ $c$ sunt orice numere mai mari decât 1, în timp ce $n$ ${\ displaystyle n}$ $n$ este indicele succesiunii.

$\log _{a}{n}\leq n^{b}\leq c^{n}\leq n!\leq n^{n}$ ${\ displaystyle \ log _ {a} {n} \ leq n ^ {b} \ leq c ^ {n} \ leq n! \ leq n ^ {n}}$ $\ log _ {a} {n} \ leq n ^ {b} \ leq c ^ {n} \ leq n! \ leq n ^ {n}$

Notă : semnul $\,\leq \,$ ${\ displaystyle \, \ leq \,}$ $\, \ leq \,$ trebuie înțeles în sensul micului o .

Alte exemple

Iată câteva exemple de ordine ale infinitului referitoare la funcții, unde $\mathop {\mathrm {Ord} } _{z}$ ${\ displaystyle \ mathop {\ mathrm {Ord}} _ {z}}$ ${\ mathop {{\ mathrm {Ord}}}} _ {z}$ indică ordinea variabilei care are tendința de $z$ ${\ displaystyle z}$ $z$ :

$\mathrm {Ord} _{+\infty }\,x^{a}\leq \mathrm {Ord} _{+\infty }\,e^{x}$ ${\ displaystyle \ mathrm {Ord} _ {+ \ infty} \, x ^ {a} \ leq \ mathrm {Ord} _ {+ \ infty} \, e ^ {x}}$ ${\ mathrm {Ord}} _ {{+ \ infty}} \, x ^ {a} \ leq {\ mathrm {Ord}} _ {{+ \ infty}} \ și ^ {x}$

$\mathrm {Ord} _{0}\,{\frac {1}{\sqrt {x}}}\leq \mathrm {Ord} _{0}\,{\frac {1}{x}}$ ${\ displaystyle \ mathrm {Ord} _ {0} \, {\ frac {1} {\ sqrt {x}}} \ leq \ mathrm {Ord} _ {0} \, {\ frac {1} {x} }}$ ${\ mathrm {Ord}} _ {0} \, {\ frac {1} {{\ sqrt x}}} \ leq {\ mathrm {Ord}} _ {0} \, {\ frac {1} {x }}$

$\mathrm {Ord} _{1}\,{\frac {1}{{\sqrt {x}}-1}}\leq \mathrm {Ord} _{1}\,{\frac {1}{x-1}}$ ${\ displaystyle \ mathrm {Ord} _ {1} \, {\ frac {1} {{\ sqrt {x}} - 1}} \ leq \ mathrm {Ord} _ {1} \, {\ frac {1 } {x-1}}}$ ${\ mathrm {Ord}} _ {1} \, {\ frac {1} {{\ sqrt x} -1}} \ leq {\ mathrm {Ord}} _ {1} \, {\ frac {1} {x-1}}$

Ordine de infinitesimal

O functie $f$ ${\ displaystyle f}$ $f$ se spune că este infinitesimal în $x_{0}$ ${\ displaystyle x_ {0}}$ $x_0$ dacă limita sa este $0$ ${\ displaystyle 0}$ ${\ displaystyle 0}$ a tinde spre $X$ ${\ displaystyle x}$ $X$ la $x_{0}$ ${\ displaystyle x_ {0}}$ $x_0$ . În simboluri, dacă $\lim _{x\to x_{0}}f(x)=0$ ${\ displaystyle \ lim _ {x \ to x_ {0}} f (x) = 0}$ $\ lim _ {{x \ to x_ {0}}} f (x) = 0$ . De exemplu ${\frac {1}{x}}$ ${\ displaystyle {\ frac {1} {x}}}$ ${\ frac {1} {x}}$ și $e^{-x}$ ${\ displaystyle e ^ {- x}}$ $și ^ {{- x}}$ sunt infinitezimale în $+\infty$ ${\ displaystyle + \ infty}$ $+ \ infty$ (primul, de asemenea, în $-\infty$ ${\ displaystyle - \ infty}$ $- \ infty$ ).

O succesiune $\{a_{n}\}$ ${\ displaystyle \ {a_ {n} \}}$ $\ {a_ {n} \}$ se spune că este infinitesimal atunci când limita sa este egală cu zero atunci când se tinde spre $n$ ${\ displaystyle n}$ $n$ la nesfârșit:

$\lim _{n\to \infty }a_{n}=0$ ${\ displaystyle \ lim _ {n \ to \ infty} a_ {n} = 0}$ $\ lim _ {{n \ to \ infty}} a_ {n} = 0$ .

Ca și în cazul infinitivelor, există secvențe care tind să zero mai repede decât altele; luând reciprocele succesiunii inegalităților de mai sus și schimbând i $\leq$ ${\ displaystyle \ leq}$ $\ leq$ în $\geq$ ${\ displaystyle \ geq}$ $\ geq$ aveți tabelul corespunzător

${\tfrac {1}{n^{n}}}\leq {\tfrac {1}{n!}}\leq {\tfrac {1}{c^{n}}}\leq {\tfrac {1}{n^{b}}}\leq {\tfrac {1}{\log _{a}n}}$ ${\ displaystyle {\ tfrac {1} {n ^ {n}}} \ leq {\ tfrac {1} {n!}} \ leq {\ tfrac {1} {c ^ {n}}} \ leq {\ tfrac {1} {n ^ {b}}} \ leq {\ tfrac {1} {\ log _ {a} n}}}$ ${\ tfrac {1} {n ^ {n}}} \ leq {\ tfrac {1} {n!}} \ leq {\ tfrac {1} {c ^ {n}}} \ leq {\ tfrac {1 } {n ^ {b}}} \ leq {\ tfrac {1} {\ log _ {a} n}}$

Notă : ordinea infinitesimală a ${\tfrac {1}{n^{n}}}$ ${\ displaystyle {\ tfrac {1} {n ^ {n}}}}$ ${\ tfrac {1} {n ^ {n}}}$ este mai mare decât cea a ${\tfrac {1}{n!}}$ ${\ displaystyle {\ tfrac {1} {n!}}}$ ${\ tfrac {1} {n!}}$ , din moment ce acesta din urmă tinde la zero mai încet .

Alte tipuri de limite

Iată câteva exemple de ordine de funcții infinitezimale:

$\mathrm {ord} _{0}\,{\sqrt {x}}\leq \mathrm {ord} _{0}\,x\leq \mathrm {ord} _{0}\,x^{2}\leq \mathrm {ord} _{0}\,x^{3}$ ${\ displaystyle \ mathrm {ord} _ {0} \, {\ sqrt {x}} \ leq \ mathrm {ord} _ {0} \, x \ leq \ mathrm {ord} _ {0} \, x ^ {2} \ leq \ mathrm {ord} _ {0} \, x ^ {3}}$ ${\ mathrm {ord}} _ {0} \, {\ sqrt {x}} \ leq {\ mathrm {ord}} _ {0} \, x \ leq {\ mathrm {ord}} _ {0} \ , x ^ {2} \ leq {\ mathrm {ord}} _ {0} \, x ^ {3}$

$\mathrm {ord} _{-\infty }\,{\frac {1}{x^{n}}}\leq \mathrm {ord} _{-\infty }\,e^{x}$ ${\ displaystyle \ mathrm {ord} _ {- \ infty} \, {\ frac {1} {x ^ {n}}} \ leq \ mathrm {ord} _ {- \ infty} \ și ^ {x} }$ ${\ mathrm {ord}} _ {{- \ infty}} \, {\ frac {1} {x ^ {n}}} \ leq {\ mathrm {ord}} _ {{- \ infty}} \, și ^ {x}$

Secvențe asimptotice

Dă două secvențe $a_{n}$ ${\ displaystyle a_ {n}}$ $a_ {n}$ Și $b_{n}$ ${\ displaystyle b_ {n}}$ $b_ {n}$ , se spune că sunt asimptotice sau asimptotice echivalente și sunt indicate cu notația $a_{n}\sim b_{n}$ ${\ displaystyle a_ {n} \ sim b_ {n}}$ $a_ {n} \ sim b_ {n}$ de sine
$\lim _{n\to \infty }{\frac {a_{n}}{b_{n}}}=1$ ${\ displaystyle \ lim _ {n \ to \ infty} {\ frac {a_ {n}} {b_ {n}}} = 1}$ $\ lim _ {{n \ to \ infty}} {\ frac {a_ {n}} {b_ {n}}} = 1$
(Evident, trebuie să presupunem că există un $Nu.$ ${\ displaystyle N}$ $Nu.$ astfel încât $b_{n}\not =0,\ \ \forall n\geq N$ ${\ displaystyle b_ {n} \ not = 0, \ \ \ forall n \ geq N}$ $b_ {n} \ not = 0, \ \ \ forall n \ geq N$ ).

În acest caz, este posibil să se creeze lanțuri de relații asimptotice:

$\mathrm {se} \,\ a_{n}\sim b_{n}\sim ...\sim c_{n}\ \,\mathrm {allora} \,\ a_{n}\sim c_{n}$ ${\ displaystyle \ mathrm {if} \, \ a_ {n} \ sim b_ {n} \ sim ... \ sim c_ {n} \ \, \ mathrm {then} \, \ a_ {n} \ sim c_ {n}}$ ${\ mathrm {se}} \, \ a_ {n} \ sim b_ {n} \ sim ... \ sim c_ {n} \ \, {\ mathrm {then}} \, \ a_ {n} \ sim c_ {n}$

O expresie compusă din produs sau coeficient de mai mulți factori poate fi estimată factor cu factor:

$\mathrm {se} \,\ a_{n}\sim a'_{n},\ b_{n}\sim b'_{n},\ c_{n}\sim c'_{n}\ \,\mathrm {allora} \,\ {\frac {a_{n}b_{n}}{c_{n}}}\sim {\frac {a'_{n}b'_{n}}{c'_{n}}}$ ${\ displaystyle \ mathrm {se} \, \ a_ {n} \ sim a '_ {n}, \ b_ {n} \ sim b' _ {n}, \ c_ {n} \ sim c '_ {n } \ \, \ mathrm {then} \, \ {\ frac {a_ {n} b_ {n}} {c_ {n}}} \ sim {\ frac {a '_ {n} b' _ {n} } {c '_ {n}}}}$ ${\ mathrm {se}} \, \ a_ {n} \ sim a '_ {n}, \ b_ {n} \ sim b' _ {n}, \ c_ {n} \ sim c '_ {n} \ \, {\ mathrm {then}} \, \ {\ frac {a_ {n} b_ {n}} {c_ {n}}} \ sim {\ frac {a '_ {n} b' _ {n }} {c '_ {n}}}$

Relația $\sim$ ${\ displaystyle \ sim}$ $\ sim$ este o relație de echivalență , deoarece proprietățile reflexive , simetrice și tranzitive cu privire la operatorul dețin.

Reguli de operare

Comparații între infinite și infinitesimale

Lasa-i sa fie $a_{n}$ ${\ displaystyle a_ {n}}$ $a_ {n}$ Și $b_{n}$ ${\ displaystyle b_ {n}}$ $b_ {n}$ două secvențe infinite. Pentru limita relației avem că dacă $\lim _{n\to +\infty }{\frac {a_{n}}{b_{n}}}$ ${\ displaystyle \ lim _ {n \ to + \ infty} {\ frac {a_ {n}} {b_ {n}}}}$ $\ lim _ {{n \ to + \ infty}} {\ frac {a_ {n}} {b_ {n}}}$ Este egal cu:

$0$ ${\ displaystyle 0}$ ${\ displaystyle 0}$ :	$a_{n}$ ${\ displaystyle a_ {n}}$ $a_ {n}$ este o infinitate de ordine mai mică decât $b_{n}$ ${\ displaystyle b_ {n}}$ $b_ {n}$
$l\not =0$ ${\ displaystyle l \ not = 0}$ $l \ not = 0$ :	$a_{n}$ ${\ displaystyle a_ {n}}$ $a_ {n}$ Și $b_{n}$ ${\ displaystyle b_ {n}}$ $b_ {n}$ sunt infinite de același ordin
$\pm \infty$ ${\ displaystyle \ pm \ infty}$ $\ pm \ infty$ :	$a_{n}$ ${\ displaystyle a_ {n}}$ $a_ {n}$ este o infinitate de ordin superior decât $b_{n}$ ${\ displaystyle b_ {n}}$ $b_ {n}$
nu exista:	$a_{n}$ ${\ displaystyle a_ {n}}$ $a_ {n}$ Și $b_{n}$ ${\ displaystyle b_ {n}}$ $b_ {n}$ nu sunt comparabile.

Implicațiile inverse mai dețin: dacă $a_{n}$ ${\ displaystyle a_ {n}}$ $a_ {n}$ domină $b_{n}$ ${\ displaystyle b_ {n}}$ $b_ {n}$ atunci limita este infinită și așa mai departe.

Același raționament poate fi repetat și pentru infinitesimale. Lasa-i sa fie $a_{n}$ ${\ displaystyle a_ {n}}$ $a_ {n}$ Și $b_{n}$ ${\ displaystyle b_ {n}}$ $b_ {n}$ două secvențe infinitesimale. Pentru limita relației avem că dacă $\lim _{n\to +\infty }{\frac {a_{n}}{b_{n}}}$ ${\ displaystyle \ lim _ {n \ to + \ infty} {\ frac {a_ {n}} {b_ {n}}}}$ $\ lim _ {{n \ to + \ infty}} {\ frac {a_ {n}} {b_ {n}}}$ Este egal cu:

$0$ ${\ displaystyle 0}$ ${\ displaystyle 0}$ :	$a_{n}$ ${\ displaystyle a_ {n}}$ $a_ {n}$ este un infinitesimal de ordin superior decât $b_{n}$ ${\ displaystyle b_ {n}}$ $b_ {n}$
$l\not =0$ ${\ displaystyle l \ not = 0}$ $l \ not = 0$ :	$a_{n}$ ${\ displaystyle a_ {n}}$ $a_ {n}$ Și $b_{n}$ ${\ displaystyle b_ {n}}$ $b_ {n}$ sunt infinitezimale de aceeași ordine
$\pm \infty$ ${\ displaystyle \ pm \ infty}$ $\ pm \ infty$ :	$a_{n}$ ${\ displaystyle a_ {n}}$ $a_ {n}$ este un infinitesimal de ordine mai mic decât $b_{n}$ ${\ displaystyle b_ {n}}$ $b_ {n}$
nu exista:	$a_{n}$ ${\ displaystyle a_ {n}}$ $a_ {n}$ Și $b_{n}$ ${\ displaystyle b_ {n}}$ $b_ {n}$ nu sunt comparabile.

Principiul substituirii infinitelor

Lasa-i sa fie $a_{n}$ ${\ displaystyle a_ {n}}$ $a_ {n}$ Și $b_{n}$ ${\ displaystyle b_ {n}}$ $b_ {n}$ doi infinitivi. La calcularea limitei raportului, infinitivele de ordin inferior pot fi adăugate sau scăzute din numărător și numitor, pe baza a ceea ce s-a văzut în paragraful anterior.

De fapt, de exemplu:

$\lim _{n\to +\infty }{\frac {n^{2}+{\sqrt {n}}}{5n^{2}-3n}}=\lim _{n\to +\infty }{\frac {n^{2}}{5n^{2}-3n}}+\lim _{n\to +\infty }{\frac {\sqrt {n}}{5n^{2}-3n}}=\lim _{n\to +\infty }{\frac {n^{2}}{5n^{2}}}+0={\frac {1}{5}}$ ${\ displaystyle \ lim _ {n \ to + \ infty} {\ frac {n ^ {2} + {\ sqrt {n}}} {5n ^ {2} -3n}} = \ lim _ {n \ to + \ infty} {\ frac {n ^ {2}} {5n ^ {2} -3n}} + \ lim _ {n \ to + \ infty} {\ frac {\ sqrt {n}} {5n ^ { 2} -3n}} = \ lim _ {n \ to + \ infty} {\ frac {n ^ {2}} {5n ^ {2}}} + 0 = {\ frac {1} {5}}}$ $\ lim _ {{n \ to + \ infty}} {\ frac {n ^ {2} + {\ sqrt n}} {5n ^ {2} -3n}} = \ lim _ {{n \ to + \ infty}} {\ frac {n ^ {2}} {5n ^ {2} -3n}} + \ lim _ {{n \ to + \ infty}} {\ frac {{\ sqrt n}} {5n ^ {2} -3n}} = \ lim _ {{n \ to + \ infty}} {\ frac {n ^ {2}} {5n ^ {2}}} + 0 = {\ frac {1} {5 }}$

Principiul de substituție a infinitesimalelor

Lasa-i sa fie $a_{n}$ ${\ displaystyle a_ {n}}$ $a_ {n}$ , $b_{n}$ ${\ displaystyle b_ {n}}$ $b_ {n}$ două secvențe infinitesimale. În calcularea limitei raportului, este posibil să se adauge sau să se scadă, într-o sumă de infinitesimale, la numărătorul și numitorul infinitesimalelor care sunt de ordin superior, pe baza a ceea ce s-a văzut în paragraful anterior.

Se obține astfel următoarea ecuație, utilă pentru rezolvarea problemelor cu limite nedeterminate:

$\lim _{n\to \infty }{\frac {a_{n}}{b_{n}}}=\lim _{n\to \infty }{\frac {a_{n}+a'_{n}}{b_{n}+b'_{n}}}$ ${\ displaystyle \ lim _ {n \ to \ infty} {\ frac {a_ {n}} {b_ {n}}} = \ lim _ {n \ to \ infty} {\ frac {a_ {n} + a '_ {n}} {b_ {n} + b' _ {n}}}}$ $\ lim _ {{n \ to \ infty}} {\ frac {a_ {n}} {b_ {n}}} = \ lim _ {{n \ to \ infty}} {\ frac {a_ {n} + a '_ {n}} {b_ {n} + b' _ {n}}}$

De exemplu:

$\lim _{n\to \infty }{\frac {n^{-2}+n^{-{\frac {1}{2}}}}{5n^{-3}-4n^{-1}}}=\lim _{n\to \infty }{\frac {n^{-{\frac {1}{2}}}}{-4n^{-1}}}=-\infty$ ${\ displaystyle \ lim _ {n \ to \ infty} {\ frac {n ^ {- 2} + n ^ {- {\ frac {1} {2}}}} {5n ^ {- 3} -4n ^ {-1}}} = \ lim _ {n \ to \ infty} {\ frac {n ^ {- {\ frac {1} {2}}}} {- 4n ^ {- 1}}} = - \ infty}$ $\ lim _ {{n \ to \ infty}} {\ frac {n ^ {{- 2}} + n ^ {{- {\ frac {1} {2}}}}} {5n ^ {{- 3 }} - 4n ^ {{- 1}}}} = \ lim _ {{n \ to \ infty}} {\ frac {n ^ {{- {\ frac {1} {2}}}}} {- 4n ^ {{- 1}}}} = - \ infty$

Principiul de substituție a echivalenților infinitesimali

Lasa-i sa fie $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ , $g(x)$ ${\ displaystyle g (x)}$ $g (x)$ două funcții infinitesimale. Pentru limita relației ${\frac {f(x)}{g(x)}}$ ${\ displaystyle {\ frac {f (x)} {g (x)}}}$ ${\ frac {f (x)} {g (x)}}$ merita

\lim _{x\to x_{0}}{\frac {f(x)}{g(x)}}=\lim _{x\to x_{0}}{\frac {h(x)}{k(x)}}

{\ displaystyle \ lim _ {x \ to x_ {0}} {\ frac {f (x)} {g (x)}} = \ lim _ {x \ to x_ {0}} {\ frac {h ( x)} {k (x)}}}

\ lim _ {{x \ to x_ {0}}} {\ frac {f (x)} {g (x)}} = \ lim _ {{x \ to x_ {0}}} {\ frac {h (x)} {k (x)}}

dacă se dovedește $f(x)\sim h(x)$ ${\ displaystyle f (x) \ sim h (x)}$ $f (x) \ sim h (x)$ Și $g(x)\sim k(x)$ ${\ displaystyle g (x) \ sim k (x)}$ $g (x) \ sim k (x)$ , adică dacă numeratorii și numitorii sunt funcții echivalente asimptotic.

De exemplu, a fi $\tan x\sim x$ ${\ displaystyle \ tan x \ sim x}$ $\ tan x \ sim x$ :

\lim _{x\to 0}{\frac {\tan x}{\sqrt {x}}}=\lim _{x\to 0}{\frac {x}{\sqrt {x}}}=0

{\ displaystyle \ lim _ {x \ to 0} {\ frac {\ tan x} {\ sqrt {x}}} = \ lim _ {x \ to 0} {\ frac {x} {\ sqrt {x} }} = 0}

\ lim _ {{x \ to 0}} {\ frac {\ tan x} {{\ sqrt x}}} = \ lim _ {{x \ to 0}} {\ frac {x} {{\ sqrt x }}} = 0

Expresii asimptotice

În evaluarea comportamentului asimptotic al unui algoritm , sunt introduse relațiile dintre secvențele numerice care au devenit frecvent utilizate. Aceste notații pot fi folosite și pentru funcții reale, cu specificarea valorii domeniului către care tinde variabila, care poate să nu fie $\infty$ ${\ displaystyle \ infty}$ $\ infty$ .

Schema generală

Definițiile pe care le vom introduce mai jos sunt multe și la prima vedere pot părea confuze sau poate fi obositor să le amintim pe toate împreună și să le comparăm între ele. Din acest motiv, adică pentru a oferi o imagine de ansamblu care este și de ajutor mnemonic, înainte de a trece la definițiile riguroase și specifice, vom ilustra într-un mod discursiv schema generală pe care se bazează toate aceste concepte.

Aproape toate definițiile pe care urmează să le introducem au următoarea structură:

Să spunem succesiunea $f(n)$ ${\ displaystyle f (n)}$ $f (n)$ e o $\mathrm {X}$ ${\ displaystyle \ mathrm {X}}$ ${\ mathrm {X}}$ a succesiunii $g(n)$ ${\ displaystyle g (n)}$ $g (n)$ , iar noi scriem

f(n)=\mathrm {X} (g(n))

{\ displaystyle f (n) = \ mathrm {X} (g (n))}

f (n) = {\ mathrm {X}} (g (n))

dacă și numai dacă:

[\mathrm {quantificatore} ]C\ \exists N\colon \ \ \ \ \forall n>N,\ \ |f(n)|\prec \succ C|g(n)|

{\ displaystyle [\ mathrm {quantifier}] C \ \ există N \ colon \ \ \ \ \ forall n> N, \ \ | f (n) | \ prec \ succ C | g (n) |}

[{\ mathrm {quantifier}}] C \ \ Exist N \ colon \ \ \ \ \ forall n> N, \ \ | f (n) | \ prev \ succ C | g (n) |

În paranteze pătrate am specificat părțile definiției care variază din când în când. În loc de [cuantificator], cele două cuantificatoare pot merge $\forall$ ${\ displaystyle \ forall}$ $\ pentru toți$ și $\exists$ ${\ displaystyle \ există}$ $\ există$ , in timp ce $\prec \succ$ ${\ displaystyle \ prec \ succ}$ $\ prev \ next$ este o relație de ordine și poate fi $\leq$ ${\ displaystyle \ leq}$ $\ leq$ sau $\geq$ ${\ displaystyle \ geq}$ $\ geq$ . Prin urmare, avem doi parametri, fiecare dintre aceștia putând asuma două valori diferite, astfel încât definițiile posibile vor fi patru:

	$\forall$ ${\ displaystyle \ forall}$ $\ pentru toți$	$\exists$ ${\ displaystyle \ există}$ $\ există$
$\leq$ ${\ displaystyle \ leq}$ $\ leq$	$\forall C\ \exists N\colon \ \ \ \ \forall n>N,\ \ \|f(n)\|\leq C\|g(n)\|$ ${\ displaystyle \ forall C \ \ există N \ colon \ \ \ \ \ forall n> N, \ \ \| f (n) \| \ leq C \| g (n) \|}$ $\ forall C \ \ există N \ colon \ \ \ \ \ forall n> N, \ \ \| f (n) \| \ leq C \| g (n) \|$	$\exists C\ \exists N\colon \ \ \ \ \forall n>N,\ \ \|f(n)\|\leq C\|g(n)\|$ ${\ displaystyle \ există C \ \ există N \ colon \ \ \ \ \ forall n> N, \ \ \| f (n) \| \ leq C \| g (n) \|}$ $\ există C \ \ există N \ colon \ \ \ \ \ pentru tot n> N, \ \ \| f (n) \| \ leq C \| g (n) \|$
$\geq$ ${\ displaystyle \ geq}$ $\ geq$	$\forall C\ \exists N\colon \ \ \ \ \forall n>N,\ \ \|f(n)\|\geq C\|g(n)\|$ ${\ displaystyle \ forall C \ \ există N \ colon \ \ \ \ \ forall n> N, \ \ \| f (n) \| \ geq C \| g (n) \|}$ $\ forall C \ \ există N \ colon \ \ \ \ \ forall n> N, \ \ \| f (n) \| \ geq C \| g (n) \|$	$\exists C\ \exists N\colon \ \ \ \ \forall n>N,\ \ \|f(n)\|\geq C\|g(n)\|$ ${\ displaystyle \ există C \ \ există N \ colon \ \ \ \ \ forall n> N, \ \ \| f (n) \| \ geq C \| g (n) \|}$ $\ există C \ \ există N \ colon \ \ \ \ \ pentru toate n> N, \ \ \| f (n) \| \ geq C \| g (n) \|$

Pentru a distinge aceste patru cazuri, simbolul trebuie, de asemenea $\mathrm {X} (\cdot )$ ${\ displaystyle \ mathrm {X} (\ cdot)}$ ${\ mathrm {X}} (\ cdot)$ care definește relația dintre $f(n)$ ${\ displaystyle f (n)}$ $f (n)$ Și $g(n)$ ${\ displaystyle g (n)}$ $g (n)$ poate presupune patru valori diferite, definite într-un fel de doi parametri: unul care definește cuantificatorul și celălalt care definește relația de ordine.

Aceste simboluri sunt după cum urmează:

$\mathrm {O}$ ${\ displaystyle \ mathrm {O}}$ ${\ mathrm {O}}$ („O grozavă”) / $\mathrm {o}$ ${\ displaystyle \ mathrm {o}}$ ${\ mathrm {o}}$ („sau mic”),
$\Omega$ ${\ displaystyle \ Omega}$ $\Omega$ („omega mare”) / $\omega$ ${\ displaystyle \ omega}$ $\omega$ („omega mic”).

După cum puteți vedea, acestea sunt de fapt patru simboluri definite de doi parametri:

Greacă latină
micul Mare

Dintre acești doi parametri, primul, adică „latină / greacă”, este utilizat pentru a specifica relația de ordine, conform următoarei asocieri:

Latin: $\leq$ ${\ displaystyle \ leq}$ $\ leq$
Greacă: $\geq$ ${\ displaystyle \ geq}$ $\ geq$

în timp ce al doilea, care este „mic / mare”, este utilizat pentru a specifica cuantificatorul, în conformitate cu următoarea asociere:

mic: $\forall$ ${\ displaystyle \ forall}$ $\ pentru toți$
Grozav: $\exists$ ${\ displaystyle \ există}$ $\ există$

Aceste asociații pot părea decisiv contraintuitive. De exemplu, ar părea mai util să asociați „mic / mare” la relațiile de ordine, astfel încât „mic” să însemne „mai mic” (adică $\leq$ ${\ displaystyle \ leq}$ $\ leq$ ) și „mare” înseamnă „mai mare (adică $\geq$ ${\ displaystyle \ geq}$ $\ geq$ ). În schimb, pentru a reda relația de ordine folosim parametrul ciudat pe care l-am definit „latină / greacă”.

Toate aceste ciudățenii aparente sunt rezolvate imediat, de îndată ce se face un pic de muncă „filologică”. În special, este important să reținem că inițial ceea ce acum numim „o” era de fapt un „omicron”, adică o altă literă greacă. De fapt, în alfabetul grecesc există două litere corespunzătoare „o” noastre:

„o-micron”, care înseamnă „sau mic”
„o-mega”, care înseamnă „sau mare”.

Prin urmare, inițial notația indica exact ceea ce intenționăm să indicăm: „micul o” („omicron”) a reprezentat $\leq$ ${\ displaystyle \ leq}$ $\ leq$ iar „marele o” („omega”) a reprezentat $\geq$ ${\ displaystyle \ geq}$ $\ geq$ .

În ceea ce privește parametrul pe care până acum l-am indicat cu „mare / mic”, știm bine că acesta este doar un mod colocvial de a face referire la literele „majuscule / mici”.

Deci, dacă ne întoarcem la utilizarea inițială a tuturor acestor simboluri, avem următoarele asociații:

„micron” („mic”): $\leq$ ${\ displaystyle \ leq}$ $\ leq$
„mega” („mare”): $\geq$ ${\ displaystyle \ geq}$ $\ geq$
„minusculă”: $\forall$ ${\ displaystyle \ forall}$ $\ pentru toți$
"majuscule": $\exists$ ${\ displaystyle \ există}$ $\ există$

	$\forall$ ${\ displaystyle \ forall}$ $\ pentru toți$	$\exists$ ${\ displaystyle \ există}$ $\ există$
$\leq$ ${\ displaystyle \ leq}$ $\ leq$	$\mathrm {o}$ ${\ displaystyle \ mathrm {o}}$ ${\ mathrm {o}}$	$\mathrm {O}$ ${\ displaystyle \ mathrm {O}}$ ${\ mathrm {O}}$
$\geq$ ${\ displaystyle \ geq}$ $\ geq$	$\omega$ ${\ displaystyle \ omega}$ $\omega$	$\Omega$ ${\ displaystyle \ Omega}$ $\Omega$

Întărit de această schemă generală, care poate fi utilă și ca regulă mnemonică, să încercăm să scriem, de exemplu, definiția următoarei expresii:

f(n)=\mathrm {O} (g(n))

{\ displaystyle f (n) = \ mathrm {O} (g (n))}

f (n) = {\ mathrm {O}} (g (n))

Trebuie să spunem că $f(n)$ ${\ displaystyle f (n)}$ $f (n)$ este un „o-micron” capital al $g(n)$ ${\ displaystyle g (n)}$ $g (n)$ . Ne amintim că:

„micron” înseamnă „mai mic”, adică $\leq$ ${\ displaystyle \ leq}$ $\ leq$ ;
„majusculă” înseamnă: $\exists$ ${\ displaystyle \ există}$ $\ există$ (Cel puțin unul) $C.$ ${\ displaystyle C}$ $C.$ astfel încât...

Iată definiția căutată:

Să spunem asta $f(n)=\mathrm {O} (g(n))$ ${\ displaystyle f (n) = \ mathrm {O} (g (n))}$ $f (n) = {\ mathrm {O}} (g (n))$ dacă și numai dacă:

\exists C\ \exists N\colon \ \ \ \ \forall n>N,\ \ |f(n)|\leq C|g(n)|

{\ displaystyle \ există C \ \ există N \ colon \ \ \ \ \ forall n> N, \ \ | f (n) | \ leq C | g (n) |}

\ există C \ \ există N \ colon \ \ \ \ \ pentru tot n> N, \ \ | f (n) | \ leq C | g (n) |

În cele din urmă, suntem interesați să cunoaștem implicațiile dintre toate aceste relații. Aceste implicații pot fi extrase imediat din următoarele considerații:

1) Amintindu-mi că, în general:

a\leq b\ \Leftrightarrow \ b\geq a

{\ displaystyle a \ leq b \ \ Leftrightarrow \ b \ geq a}

a \ leq b \ \ Leftrightarrow \ b \ geq a

asa de $f$ ${\ displaystyle f}$ $f$ este un "omicron" (adică "mai mic") decât $g$ ${\ displaystyle g}$ $g$ dacă și numai dacă $g$ ${\ displaystyle g}$ $g$ este un "omega" (adică "mai mare") decât $f$ ${\ displaystyle f}$ $f$ :

f(x)=\mathrm {O} /\mathrm {o} (g(x))\ \Leftrightarrow \ g(x)=\Omega /\omega (f(x))

{\ displaystyle f (x) = \ mathrm {O} / \ mathrm {o} (g (x)) \ \ Leftrightarrow \ g (x) = \ Omega / \ omega (f (x))}

f (x) = {\ mathrm {O}} / {\ mathrm {o}} (g (x)) \ \ Leftrightarrow \ g (x) = \ Omega / \ omega (f (x))

2) Dacă o relație este adevărată $\forall C$ ${\ displaystyle \ forall C}$ $\ forall C$ apoi în special $\exists$ ${\ displaystyle \ există}$ $\ există$ un anumit $C.$ ${\ displaystyle C}$ $C.$ asta te mulțumește. Deci, dacă o succesiune $f(n)$ ${\ displaystyle f (n)}$ $f (n)$ este o „minusculă” a secvenței $g(n)$ ${\ displaystyle g (n)}$ $g (n)$ atunci este și „capital” al acestuia:

f(x)=\mathrm {o} /\omega (g(x))\ \Rightarrow \ f(x)=\mathrm {O} /\Omega (g(x))

{\ displaystyle f (x) = \ mathrm {o} / \ omega (g (x)) \ \ Rightarrow \ f (x) = \ mathrm {O} / \ Omega (g (x))}

f (x) = {\ mathrm {o}} / \ omega (g (x)) \ \ Rightarrow \ f (x) = {\ mathrm {O}} / \ Omega (g (x))

Acest lucru poate fi exprimat și spunând că setul „minuscule” al unei anumite funcții este conținut în setul „majuscule” al acelei funcții și acest lucru se aplică și ca regulă mnemonică pentru parametrul „majusculă / minusculă”.

Sau mare

Același subiect în detaliu: O-mare .

Lasa-i sa fie $f$ ${\ displaystyle f}$ $f$ Și $g$ ${\ displaystyle g}$ $g$ două funcții definite pe $\mathbb {N}$ ${\ displaystyle \ mathbb {N}}$ $\ N$ la valori în $\mathbb {R}$ ${\ displaystyle \ mathbb {R}}$ $\ R$ .

Se spune că $f(n)$ ${\ displaystyle f (n)}$ $f (n)$ este o o mare de $g(n)$ ${\ displaystyle g (n)}$ $g (n)$ , în simboluri

$f(n)=\mathrm {O} (g(n))$ ${\ displaystyle f (n) = \ mathrm {O} (g (n))}$ $f (n) = {\ mathrm {O}} (g (n))$

de sine $\exists c>0,n_{0}\in N\colon \ \ \ \ \forall n\geq n_{0},\ \ |f(n)|\leq c|g(n)|$ ${\ displaystyle \ există c> 0, n_ {0} \ în N \ colon \ \ \ \ \ \ forall n \ geq n_ {0}, \ \ | f (n) | \ leq c | g (n) | }$ $\ există c> 0, n_ {0} \ în N \ colon \ \ \ \ \ forall n \ geq n_ {0}, \ \ | f (n) | \ leq c | g (n) |$ .

Se mai spune că $f(n)$ ${\ displaystyle f (n)}$ $f (n)$ are un ordin de mărime mai mic sau egal cu cel al $g(n)$ ${\ displaystyle g (n)}$ $g (n)$ , aceasta este funcția $g(n)$ ${\ displaystyle g (n)}$ $g (n)$ domină $f(n)$ ${\ displaystyle f (n)}$ $f (n)$ .

Dacă succesiunea $g(n)$ ${\ displaystyle g (n)}$ $g (n)$ are valori definitiv diferite de zero, o condiție echivalentă, exploatând limita superioară , este că este $\limsup _{n\to \infty }\left|{\frac {f(n)}{g(n)}}\right|<\infty$ ${\ displaystyle \ limsup _ {n \ to \ infty} \ left | {\ frac {f (n)} {g (n)}} \ right | <\ infty}$ $\ limsup _ {{n \ to \ infty}} \ left | {\ frac {f (n)} {g (n)}} \ right | <\ infty$ .

Exemple

$n=\mathrm {O} \left(2n\right)$ ${\ displaystyle n = \ mathrm {O} \ left (2n \ right)}$ ${\ displaystyle n = \ mathrm {O} \ left (2n \ right)}$

$n=\mathrm {O} \left({\frac {n}{2}}\right)$ ${\ displaystyle n = \ mathrm {O} \ left ({\ frac {n} {2}} \ right)}$ $n = \ mathrm {O} \ left (\ frac {n} {2} \ right)$

$4n^{2}+n=\mathrm {O} (n^{2})$ ${\ displaystyle 4n ^ {2} + n = \ mathrm {O} (n ^ {2})}$ $4n ^ {2} + n = {\ mathrm {O}} (n ^ {2})$

$n\log n\neq \mathrm {O} (n)$ ${\ displaystyle n \ log n \ neq \ mathrm {O} (n)}$ $n \ log n \ neq {\ mathrm {O}} (n)$

Sau mici

Se spune că $f(n)$ ${\ displaystyle f (n)}$ $f (n)$ este un o-mic de $g(n)$ ${\ displaystyle g (n)}$ $g (n)$ , în simboluri

$f(n)=\mathrm {o} (g(n))$ ${\ displaystyle f (n) = \ mathrm {o} (g (n))}$ $f (n) = {\ mathrm {o}} (g (n))$

de sine $\lim _{n\to \infty }{\frac {f(n)}{g(n)}}=0$ ${\ displaystyle \ lim _ {n \ to \ infty} {\ frac {f (n)} {g (n)}} = 0}$ $\ lim _ {{n \ to \ infty}} {\ frac {f (n)} {g (n)}} = 0$

Omega mare

Se spune că $f(n)$ ${\ displaystyle f (n)}$ $f (n)$ este un mare omega de $g(n)$ ${\ displaystyle g (n)}$ $g (n)$ , în simboluri

$f(n)=\Omega (g(n))$ ${\ displaystyle f (n) = \ Omega (g (n))}$ $f (n) = \ Omega (g (n))$

de sine $\exists c>0,n_{0}\in \mathbb {N} \colon \ \ \ \ \forall n\geq n_{0},\ \ |f(n)|\geq c|g(n)|$ ${\ displaystyle \ există c> 0, n_ {0} \ in \ mathbb {N} \ colon \ \ \ \ \ forall n \ geq n_ {0}, \ \ | f (n) | \ geq c | g ( n) |}$ $\ există c> 0, n_ {0} \ în \ mathbb {N} \ colon \ \ \ \ \ forall n \ geq n_ {0}, \ \ | f (n) | \ geq c | g (n) |$ .

Se mai spune că $f(n)$ ${\ displaystyle f (n)}$ $f (n)$ are un ordin de mărime mai mare sau egal cu cel al $g(n)$ ${\ displaystyle g (n)}$ $g (n)$ , sau asta $g(n)$ ${\ displaystyle g (n)}$ $g (n)$ este dominat de $f(n)$ ${\ displaystyle f (n)}$ $f (n)$ .

Folosind notația de limită inferioară , o condiție echivalentă este că este $\liminf _{n\to \infty }\left|{\frac {f(n)}{g(n)}}\right|>0$ ${\ displaystyle \ liminf _ {n \ to \ infty} \ left | {\ frac {f (n)} {g (n)}} \ right |> 0}$ $\ liminf _ {{n \ to \ infty}} \ left | {\ frac {f (n)} {g (n)}} \ right |> 0$

Omega mic

Se spune că $f(n)$ ${\ displaystyle f (n)}$ $f (n)$ este un mic omega de $g(n)$ ${\ displaystyle g (n)}$ $g (n)$ , în simboluri

$f(n)=\omega (g(n))$ ${\ displaystyle f (n) = \ omega (g (n))}$ $f (n) = \ omega (g (n))$

de sine $\lim _{n\to \infty }{\frac {f(n)}{g(n)}}=\infty$ ${\ displaystyle \ lim _ {n \ to \ infty} {\ frac {f (n)} {g (n)}} = \ infty}$ $\ lim _ {{n \ to \ infty}} {\ frac {f (n)} {g (n)}} = \ infty$

Theta

$f(n)$ ${\ displaystyle f (n)}$ $f (n)$ Și $g(n)$ ${\ displaystyle g (n)}$ $g (n)$ se spune că au același ordin de mărime, în simboluri

$f(n)=\Theta (g(n))$ ${\ displaystyle f (n) = \ Theta (g (n))}$ $f (n) = \ Theta (g (n))$

de sine $\exists c_{1},c_{2}>0,n_{0}\in \mathbb {N} \colon \ \ \ \ \forall n\geq n_{0},\ \ c_{1}|g(n)|\leq |f(n)|\leq c_{2}|g(n)|$ ${\ displaystyle \ există c_ {1}, c_ {2}> 0, n_ {0} \ in \ mathbb {N} \ colon \ \ \ \ \ forall n \ geq n_ {0}, \ \ c_ {1 } | g (n) | \ leq | f (n) | \ leq c_ {2} | g (n) |}$ $\ există c_ {1}, c_ {2}> 0, n_ {0} \ în \ mathbb {N} \ colon \ \ \ \ \ forall n \ geq n_ {0}, \ \ c_ {1} | g ( n) | \ leq | f (n) | \ leq c_ {2} | g (n) |$ .

Folosind limitele superioare și inferioare, această condiție poate fi declarată ca $0<\liminf _{n\to \infty }\left|{\frac {f(n)}{g(n)}}\right|\leq \limsup _{n\to \infty }\left|{\frac {f(n)}{g(n)}}\right|<\infty$ ${\ displaystyle 0 <\ liminf _ {n \ to \ infty} \ left | {\ frac {f (n)} {g (n)}} \ right | \ leq \ limsup _ {n \ to \ infty} \ left | {\ frac {f (n)} {g (n)}} \ right | <\ infty}$ $0 <\ liminf _ {{n \ to \ infty}} \ left | {\ frac {f (n)} {g (n)}} \ right | \ leq \ limsup _ {{n \ to \ infty}} \ left | {\ frac {f (n)} {g (n)}} \ right | <\ infty$ ->

Proprietățile expresiilor asimptotice

Următoarele proprietăți se aplică expresiilor asimptotice:

Proprietăți de bază

$f=\mathrm {O} (g)\iff g=\Omega (f)$ ${\ displaystyle f = \ mathrm {O} (g) \ if g = \ Omega (f)}$ $f = {\ mathrm {O}} (g) \ if g = \ Omega (f)$ .
$f=\mathrm {o} (g)\iff g=\omega (f)$ ${\ displaystyle f = \ mathrm {o} (g) \ if g = \ omega (f)}$ $f = {\ mathrm {o}} (g) \ if g = \ omega (f)$ .
$f=\mathrm {O} (f)$ ${\ displaystyle f = \ mathrm {O} (f)}$ $f = {\ mathrm {O}} (f)$ .
$f=\mathrm {o} (f)\ \Rightarrow \ f\equiv 0$ ${\ displaystyle f = \ mathrm {o} (f) \ \ Rightarrow \ f \ equiv 0}$ $f = {\ mathrm {o}} (f) \ \ Rightarrow \ f \ equiv 0$ .

Implicații

$g=\mathrm {o} (f)\ \Rightarrow \ g=\mathrm {O} (f)$ ${\ displaystyle g = \ mathrm {o} (f) \ \ Rightarrow \ g = \ mathrm {O} (f)}$ $g = {\ mathrm {o}} (f) \ \ Rightarrow \ g = {\ mathrm {O}} (f)$ .
acesta este: $o(f)\subseteq \mathrm {O} (f)$ ${\ displaystyle o (f) \ subseteq \ mathrm {O} (f)}$ $o (f) \ subseteq {\ mathrm {O}} (f)$ .
$f=\mathrm {O} (g)\ \not \Rightarrow \ f=\mathrm {o} (g)$ ${\ displaystyle f = \ mathrm {O} (g) \ \ not \ Rightarrow \ f = \ mathrm {o} (g)}$ $f = {\ mathrm {O}} (g) \ \ not \ Rightarrow \ f = {\ mathrm {o}} (g)$ .

Sume de funcții

$\mathrm {O} (f)+\mathrm {O} (g)=\mathrm {O} (\max \lbrace |f|,|g|\rbrace )$ ${\ displaystyle \ mathrm {O} (f) + \ mathrm {O} (g) = \ mathrm {O} (\ max \ lbrace | f |, | g | \ rbrace)}$ ${\ mathrm {O}} (f) + {\ mathrm {O}} (g) = {\ mathrm {O}} (\ max \ lbrace | f |, | g | \ rbrace)$ .
$\mathrm {O} (kg)=\mathrm {O} (g),\ \forall k\in \mathbb {R} _{0}$ ${\ displaystyle \ mathrm {O} (kg) = \ mathrm {O} (g), \ \ forall k \ in \ mathbb {R} _ {0}}$ ${\ mathrm {O}} (kg) = {\ mathrm {O}} (g), \ \ forall k \ in \ mathbb {R} _ {0}$ .
$\mathrm {O} (f)+\mathrm {O} (f)=\mathrm {O} (f)$ ${\ displaystyle \ mathrm {O} (f) + \ mathrm {O} (f) = \ mathrm {O} (f)}$ ${\ mathrm {O}} (f) + {\ mathrm {O}} (f) = {\ mathrm {O}} (f)$ .
acesta este $g=\mathrm {O} (f)\land h=\mathrm {O} (f)\ \Rightarrow g+h=\mathrm {O} (f)$ ${\ displaystyle g = \ mathrm {O} (f) \ land h = \ mathrm {O} (f) \ \ Rightarrow g + h = \ mathrm {O} (f)}$ $g = {\ mathrm {O}} (f) \ land h = {\ mathrm {O}} (f) \ \ Rightarrow g + h = {\ mathrm {O}} (f)$ .
$\mathrm {O} (f)+\mathrm {o} (f)=\mathrm {O} (f)$ ${\ displaystyle \ mathrm {O} (f) + \ mathrm {o} (f) = \ mathrm {O} (f)}$ ${\ mathrm {O}} (f) + {\ mathrm {o}} (f) = {\ mathrm {O}} (f)$ .
$\mathrm {o} (f)+\mathrm {o} (f)=\mathrm {o} (f)$ ${\ displaystyle \ mathrm {o} (f) + \ mathrm {o} (f) = \ mathrm {o} (f)}$ ${\ mathrm {o}} (f) + {\ mathrm {o}} (f) = {\ mathrm {o}} (f)$ .

Produse

$\mathrm {O} (f)\mathrm {O} (g)=\mathrm {O} (fg)$ ${\ displaystyle \ mathrm {O} (f) \ mathrm {O} (g) = \ mathrm {O} (fg)}$ ${\ mathrm {O}} (f) {\ mathrm {O}} (g) = {\ mathrm {O}} (fg)$
acesta este $h=\mathrm {O} (f)\land k=\mathrm {O} (g)\ \Rightarrow hk=\mathrm {O} (fg)$ ${\ displaystyle h = \ mathrm {O} (f) \ land k = \ mathrm {O} (g) \ \ Rightarrow hk = \ mathrm {O} (fg)}$ $h = {\ mathrm {O}} (f) \ land k = {\ mathrm {O}} (g) \ \ Rightarrow hk = {\ mathrm {O}} (fg)$ .
$\mathrm {O} (f)\mathrm {o} (g)=\mathrm {o} (fg)$ ${\ displaystyle \ mathrm {O} (f) \ mathrm {o} (g) = \ mathrm {o} (fg)}$ ${\ mathrm {O}} (f) {\ mathrm {o}} (g) = {\ mathrm {o}} (fg)$ .
$\mathrm {o} (f)\mathrm {o} (g)=\mathrm {o} (fg)$ ${\ displaystyle \ mathrm {o} (f) \ mathrm {o} (g) = \ mathrm {o} (fg)}$ ${\ mathrm {o}} (f) {\ mathrm {o}} (g) = {\ mathrm {o}} (fg)$ .

În plus față de acestea, în cadrul fiecăreia dintre notații deține proprietatea tranzitivă , adică, de exemplu, dacă $f=\mathrm {O} (g)$ ${\ displaystyle f = \ mathrm {O} (g)}$ $f = {\ mathrm {O}} (g)$ Și $g=\mathrm {O} (h)$ ${\ displaystyle g = \ mathrm {O} (h)}$ $g = {\ mathrm {O}} (h)$ asa de $f=\mathrm {O} (h)$ ${\ displaystyle f = \ mathrm {O} (h)}$ $f = {\ mathrm {O}} (h)$ .

Reflexivitatea și tranzitivitatea $\mathrm {O}$ ${\ displaystyle \ mathrm {O}}$ ${\ mathrm {O}}$ ele implică faptul că este o precomandă , a cărei relație de echivalență asociată este adecvată $\Theta$ ${\ displaystyle \ Theta}$ $\ Theta$ . De fapt din definiția $\Theta$ ${\ displaystyle \ Theta}$ $\ Theta$ , este exact $f=\Theta (g)\iff f=\mathrm {O} (g)\land g=\mathrm {O} (f)$ ${\ displaystyle f = \ Theta (g) \ if f = \ mathrm {O} (g) \ land g = \ mathrm {O} (f)}$ $f = \ Theta (g) \ if f = {\ mathrm {O}} (g) \ land g = {\ mathrm {O}} (f)$ .

De asemenea, dacă $p$ ${\ displaystyle p}$ $p$ este o constantă, este cu siguranță $f(x)\leq p$ ${\ displaystyle f (x) \ leq p}$ $f (x) \ leq p$ dacă și numai dacă $f(n)=\mathrm {O} (1)$ ${\ displaystyle f (n) = \ mathrm {O} (1)}$ $f (n) = {\ mathrm {O}} (1)$ și în mod similar este cu siguranță $f\geq p$ ${\ displaystyle f \ geq p}$ $f \ geq p$ dacă și numai dacă $f(n)=\Omega (1)$ ${\ displaystyle f (n) = \ Omega (1)}$ $f (n) = \ Omega (1)$ .

Probleme de notare

Afirmația $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ este o o mare de $g(x)$ ${\ displaystyle g (x)}$ $g (x)$ se scrie de obicei ca $f(x)=\mathrm {O} (g(x))$ ${\ displaystyle f (x) = \ mathrm {O} (g (x))}$ $f (x) = {\ mathrm {O}} (g (x))$ . Aceasta este o ușoară utilizare greșită a notației, deoarece egalitatea celor două funcții nu este afirmată. În plus, proprietatea nu este simetrică:

\mathrm {O} (x)=\mathrm {O} (x^{2})\ \ \mathrm {ma} \ \ \mathrm {O} (x^{2})\neq \mathrm {O} (x)

{\ displaystyle \ mathrm {O} (x) = \ mathrm {O} (x ^ {2}) \ \ \ mathrm {ma} \ \ \ mathrm {O} (x ^ {2}) \ neq \ mathrm { O} (x)}

{\ mathrm {O}} (x) = {\ mathrm {O}} (x ^ {2}) \ \ {\ mathrm {ma}} \ \ {\ mathrm {O}} (x ^ {2}) \ neq {\ mathrm {O}} (x)

.

Din acest motiv, unii autori preferă notația setului și scriu $f\in \mathrm {O} (g)$ ${\ displaystyle f \ in \ mathrm {O} (g)}$ $f \ in {\ mathrm {O}} (g)$ , gindind despre $\mathrm {O} (g)$ ${\ displaystyle \ mathrm {O} (g)}$ ${\ mathrm {O}} (g)$ în ceea ce privește clasa tuturor funcțiilor dominate de $g$ ${\ displaystyle g}$ $g$ , sau utilizează o notație introdusă de Hardy , care este următoarea:

f\lesssim g\iff f\in \mathrm {O} (g)

{\ displaystyle f \ lesssim g \ if f \ in \ mathrm {O} (g)}

f \ lesssim g \ if f \ in {\ mathrm {O}} (g)

Și

f\ll g\iff f\in \mathrm {o} (g)

{\ displaystyle f \ ll g \ if f \ in \ mathrm {o} (g)}

f \ ll g \ if f \ in {\ mathrm {o}} (g)

.

Grafice

Exemplu de notare O mare: f (x) = O (g (x)), există c > 0 și o valoare x ₀ astfel încât în dreapta lui x ₀ avem f (x) <cg (x)

Exemplu de notație Ω-mare: f (x) = Ω (g (x)), există c > 0 și o valoare x ₀ astfel încât în dreapta lui x ₀ avem f (x)> cg (x)

Elemente conexe

Portale Matematica : accedi alle voci di Wikipedia che trattano di matematica

V · D · M Analiza matematică
Calcul infinitesimal	Număr real · infinitesimal · O mare · Succesiune ( de funcții ) · Succesiunea lui Cauchy · teorema Bolzano-Weierstrass · estimare asimptotică · Limită ( o funcție · o succesiune · formă nedeterminată ) · Teorema a doi polițiști · Limită considerabilă · punct de acumulare · punct izolat · În jurul valorii · Serie ( funcție ) · criterii de convergență ·limită a funcțiilor multivariate
Studio della continuità	Funzione continua · Punto di discontinuità · Continuità uniforme · Funzione lipschitziana · Teorema di Bolzano · Teorema di Weierstrass · Teorema dei valori intermedi · Teorema di Heine-Cantor · Modulo di continuità · Funzione semicontinua · Continuità separata · Teorema di approssimazione di Weierstrass
Calcolo differenziale	Derivata · Differenziale · Regole di derivazione · Teorema di Fermat · Teorema di Rolle · Teorema di Lagrange · Teorema di Cauchy · Teorema di Darboux · Teorema di Taylor · Serie di Taylor · Funzione differenziabile · Gradiente · Jacobiana · Hessiana · Forma differenziale · Generalizzazioni della derivata · Derivata parziale · Derivata mista
Integrale	Primitiva · Integrale di Riemann · Integrale improprio · Integrale di Lebesgue · Teorema fondamentale · Metodi di integrazione · Tavole · Integrale multiplo , di linea ( 1ª specie · 2ª specie ) e di superficie ( di volume )
Studio di funzione	Funzione · Variabile · Dominio e codominio · Funzioni pari e dispari · Funzione periodica · Funzione monotona · Funzione convessa · Massimo e minimo di una funzione · Punto angoloso · Cuspide · Punto di flesso · Asintoto · Grafico di una funzione · Funzione iniettiva
Disuguaglianze	Disuguaglianza triangolare · Disuguaglianza di Cauchy-Schwarz · Bernoulli · Jensen · Hölder · Young · Minkowski
Altro	Approssimazione di Stirling · Prodotto di Wallis · Funzione Gamma · Teorema delle funzioni implicite · Teorema della funzione inversa · Funzione hölderiana · Spazio metrico · Spazio normato · Intervallo · Insieme trascurabile · Insieme chiuso · Insieme aperto · Palla · Omeomorfismo · Omeomorfismo locale · Diffeomorfismo · Diffeomorfismo locale · Classe C di una funzione · Equazione differenziale · Problema di Cauchy