„O” mare și „o” mic

„O” mare și „o” mic ( și ) sunt notații matematice pentru compararea comportamentului asimptotic (asimptotice) al funcțiilor . Ele sunt utilizate în diferite ramuri ale matematicii, dar cel mai activ - în analiza matematică , teoria numerelor și combinatorică , precum și în informatică și teoria algoritmilor . Asimptotica este înțeleasă ca natura modificării unei funcții, deoarece argumentul acesteia tinde către un anumit punct. $O$ $o$

$de)$ , " o mic de " înseamnă " infinit mic în ceea ce privește " [1] , neglijabil când se consideră . Semnificația termenului „O mare” depinde de domeniul său de aplicare, dar nu crește întotdeauna mai repede decât (definițiile exacte sunt date mai jos). $f$ $f$ $f$ $De)$ $f$

În special:

Expresia „ complexitatea algoritmului este ” înseamnă că, odată cu o creștere a parametrului care caracterizează cantitatea de informații de intrare a algoritmului, timpul de rulare a algoritmului nu va crește mai repede decât înmulțit cu o constantă; $O(f(n))$ $n$ $f(n)$
expresia „funcția este” o „mică a funcției în vecinătatea punctului ” înseamnă că pe măsură ce k este apropiat , acesta scade mai repede decât (raportul tinde spre zero). $f(x)$ $g(x)$ $p$ $X$ $p$ $f(x)$ $g(x)$ $\left |f(x)\dreapta |/\left |g(x)\dreapta |$

Definiții

Fie și două funcții definite într-o vecinătate perforată a punctului și în această vecinătate nu dispare. Ei spun că: $f(x)$ $g(x)$ $x_{0}$ $g$

$f$ este „O” mai mare decât atunci când , dacă există o astfel de constantă încât pentru toți dintr-o vecinătate a punctului inegalitatea este valabilă $g$ $x\la x_0$ $C>0$ $X$ $x_{0}$ $|f(x)| \leqslant C |g(x)|$ ;
$f$ este „o” mic de la , dacă pentru oricare există o vecinătate atât de perforată a punctului încât inegalitatea este valabilă pentru toate $g$ $x\la x_0$ $\varepsilon >0$ $U_{x_0}'$ $x_{0}$ $x\în U_{x_0}'$ $|f(x)| < \varepsilon |g(x)|.$

Cu alte cuvinte, în primul caz, raportul se află în vecinătatea punctului (adică este mărginit de sus), iar în al doilea caz, tinde spre zero la . ${\frac {|f|}{|g|}}\leqslant C$ $x_{0}$ $x\la x_0$

Denumire

De obicei, expresia „ este mare ( mică) din „ este scrisă folosind egalitatea (respectiv, ). $f$ $O$ $o$ $g$ $f(x) = O(g(x))$ $f(x) = o(g(x))$

Această notație este foarte convenabilă, dar necesită o anumită atenție în utilizarea sa (și, prin urmare, poate fi evitată în cele mai elementare manuale). Cert este că aceasta nu este egalitate în sensul obișnuit, ci o relație asimetrică .

În special, se poate scrie

f(x) = O(g(x))

(sau ),

f(x) = o(g(x))

ci expresii

O(g(x)) = f(x)

(sau )

o(g(x)) = f(x)

fără înţeles.

Un alt exemplu: dacă este adevărat că $x\rightarrow 0$

O(x^2) = o(x)

dar

o(x)\neq O(x^{2})

Pentru orice x este adevărat

o(x) = O(x)

adică o mărime infinitezimală este mărginită, dar

O(x)\neq o(x).

În loc de semnul egal, ar fi mai corect din punct de vedere metodologic să se utilizeze semnele de apartenență și includere, înțelegând și ca desemnări pentru seturi de funcții, adică folosind notația sub forma $O({\,})$ $o({\,})$

x^{3}+x^{2}\în O(x^{3})

\mathop O(x^2)\subset o(x)

în loc de, respectiv,

x^{3}+x^{2}=O(x^{3})

și

\mathop O(x^2) = o(x)

Cu toate acestea, în practică, o astfel de înregistrare este extrem de rară, mai ales în cele mai simple cazuri.

Atunci când se utilizează aceste notații, trebuie să se precizeze în mod explicit (sau evident din context) care vecinătăți (uni sau cu două fețe; care conțin numere întregi, reale, complexe sau alte numere) și ce seturi admisibile de funcții sunt în discuție (deoarece aceleași notația este utilizată în raport cu funcțiile mai multor variabile, cu funcțiile unei variabile complexe, cu matrice etc.).

Alte denumiri similare

Următoarea notație este utilizată pentru funcții și pentru : $f(n)$ $g(n)$ $n \la n_0$

Desemnare	Explicație intuitivă	Definiție
$f(n)\în O(g(n))$	$f$ este mărginită de sus de o funcție (până la un factor constant) asimptotic $g$	$\exists (C>0), U : \forall (n \in U) \; \|f(n)\| \leq C\|g(n)\|$
$f(n)\in \Omega (g(n))$	$f$ este mărginită de jos de o funcție (până la un factor constant) asimptotic $g$	$\exists (C>0), U : \forall (n \in U) \; C\|g(n)\| \leq \|f(n)\|$
$f(n)\în \Theta (g(n))$	$f$ mărginit de jos și de sus de funcție asimptotic $g$	$\exists (C>0), (C'>0), U : \forall (n \in U) \; C\|g(n)\| \leq \|f(n)\| \leq C'\|g(n)\|$
$f(n)\în o(g(n))$	$g$ domină asimptotic $f$	$\forall (C>0) ,\exists U : \forall(n \in U) \; \|f(n)\| < C\|g(n)\|$
$f(n)\in \omega (g(n))$	$f$ domină asimptotic $g$	$\forall (C>0) ,\exists U : \forall(n \in U) \; C\|g(n)\| < \|f(n)\|$
$f(n) ~\sim~ g(n)$	$f$ este echivalent asimptotic $g$	$\lim_{n \to n_0} \frac{f(n)}{g(n)} = 1$

unde este vecinătatea perforată a punctului . $U$ $n_{0}$

Proprietăți de bază

Tranzitivitate

${\begin{matrix}f(n)=\Theta (g(n))\land g(n)=\Theta (h(n))&\implies &f(n)=\Theta (h( n))\\f(n)=O(g(n))\land g(n)=O(h(n))&\implies &f(n)=O(h(n))\\f( n)=\Omega (g(n))\land g(n)=\Omega (h(n))&\implies &f(n)=\Omega (h(n))\\f(n)=o (g(n))\land g(n)=o(h(n))&\implies &f(n)=o(h(n))\\f(n)=\omega (g(n)) \land g(n)=\omega (h(n))&\implies &f(n)=\omega (h(n))\end{matrice}}$

Reflexivitate

$f(n)=\Theta(f(n))$ ; ; $f(n)=O(f(n))$ $f(n)=\Omega(f(n))$

Simetrie

$f(n)=\Theta(g(n)) \Săgeată la stânga g(n)=\Theta(f(n))$

Simetria permutației

$\begin{matrice} f(n)= O(g(n)) & \Leftrightarrow & g(n)=\Omega(f(n)) \\ f(n)= o(g(n)) & \ Săgeată stânga la dreapta și g(n)=\omega(f(n)) \end{matrice}$

Altele

$C\cdot o(f) = o(f)$

C\cdot O(f) = O(f)

$o(C \cdot f) = o(f)$

O(C \cdot f) = O(f)

si, in consecinta,

o(-f) = o(f)

O(-f) = O(f)

$o(f) + o(f) = o(f)$

o(f) + O(f) = O(f) + O(f) = O(f)

$O(f) \cdot O(g) = O(fg)$

o(f) \cdot O(g) = o(f) \cdot o(g) = o(fg)

$O(O(f)) = O(f)$

o(o(f)) = o(O(f)) = O(o(f)) = o(f)

Notație asimptotică în ecuații

Dacă partea dreaptă a ecuației conține doar notația asimptotică (de exemplu ), atunci semnul egal denotă apartenența la mulțime ( ). $n=O(n^{2})$ $n\în O(n^{2})$
Dacă notația asimptotică apare într-o ecuație în altă situație, acestea sunt tratate ca înlocuind unele funcții pentru ele. De exemplu, ca x → 0, formula înseamnă că , unde este o funcție despre care se știe doar că aparține mulțimii . Se presupune că există atâtea astfel de funcții într-o expresie câte notații asimptotice sunt în ea. De exemplu, - conține o singură funcție din . $e^x-1 = x + o(x)$ $e^x-1 = x + f(x)$ $f(x)$ $bou)$ $\sum_{i=0}^nO(n_i^2)$ $O(n^{2})$
Dacă notația asimptotică apare în partea stângă a ecuației, se folosește următoarea regulă:
orice funcții alegem (conform regulii anterioare) în loc de notația asimptotică din partea stângă a ecuației, putem alege funcții în loc de notație asimptotică (conform regulii anterioare) pe partea dreaptă, astfel încât ecuația să fie corectă .
De exemplu, intrarea înseamnă că pentru orice funcție , există o funcție astfel încât expresia să fie adevărată pentru toate . $x+o(x)=O(x)$ $f(x)\în o(x)$ $g(x)\în O(x)$ $x+f(x)=g(x)$ $X$
Mai multe dintre aceste ecuații pot fi combinate în lanțuri. Fiecare dintre ecuațiile din acest caz trebuie interpretată în conformitate cu regula anterioară.
De exemplu: . Rețineți că o astfel de interpretare implică îndeplinirea relației . $4n^4+4n^2+1=4n^4+\Theta(n^2)=\Theta(n^4)$ $4n^4+4n^2+1=\Theta(n^4)$

Interpretarea de mai sus implică îndeplinirea relației:

\stânga. \begin{matrice}A = B \\ B = C \end{matrice} \right\} \Rightarrow A = C

, unde A , B , C sunt expresii care pot conține notație asimptotică.

Exemple de utilizare

$e^{x}=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+\ldots +{\frac {x^{n}}{n!}}+\ldots =1+x+{\frac {x^{2}}{2}}+O(x^{3})$ la . $x\rightarrow 0$

$n! = O\left(\left(\frac{n}{e}\right)^{n + \frac{1}{2}}\right)$ la (urmează din formula Stirling ) $n \rightarrow \infty$

$T(n)=(n+1)^2=O(n^2)$ la . $n \rightarrow \infty$

Când inegalitatea este îndeplinită . Deci hai sa punem .

n>1

(n+1)^2<4n^2

n_0=1, c=4

Rețineți că nu putem pune , deoarece și, prin urmare, această valoare este mai mare decât , pentru orice constantă .

n_{0}=0

T(0)=1

c

c \cdot 0^2=0

Funcția pentru are un grad de creștere . $T(n)=3n^3+2n^2$ $n \rightarrow \infty$ $O(n^{3})$

Pentru a arăta acest lucru, trebuie să punem și . Se poate spune, desigur, că are ordine , dar aceasta este o afirmație mai slabă decât asta .

n_{0}=0

c=5

T(n)

O(n^{4})

T(n) = O(n^3)

Să demonstrăm că funcția pentru nu poate avea ordinea . $3^n$ $n \rightarrow \infty$ $O(2^n)$

Să presupunem că există constante și astfel încât inegalitatea este valabilă pentru toți .

c

n_{0}

n \geq n_0

3^n \leq c \cdot 2^n

Apoi pentru toți . Dar capătă orice valoare, arbitrar mare, pentru suficient de mare , așa că nu există o astfel de constantă care ar putea majora pentru toate marile dintre unele .

c \geq \left( \frac{3}{2} \right)^n

n \geq n_0

\left( \frac{3}{2} \right)^n

n

c

\left( \frac{3}{2} \right)^n

n

n_{0}

$T(n)=n^3+2n^2 = \Omega(n^3), n \rightarrow \infty$ .

Pentru a verifica, pune doar . Apoi pentru .

c=1

T(n) \geq cn^3

n=0, 1,...

Istorie

Notația „O” este mare, introdusă de matematicianul german Paul Bachmann în al doilea volum al cărții sale „Analytische Zahlentheorie” (Teoria analitică a numerelor), publicată în 1894 . Notația „o mic” a fost folosită pentru prima dată de un alt matematician german, Edmund Landau , în 1909 ; popularizarea ambelor denumiri este, de asemenea, legată de lucrările acestuia din urmă, în legătură cu care sunt numite și simboluri Landau . Denumirea provine de la cuvântul german „Ordnung” (ordine) [2] .

Vezi și

infinitezimal

Note

↑ Shvedov I. A. Curs compact de analiză matematică. Partea 1. Funcțiile unei variabile. - Novosibirsk, 2003. - S. 43.
↑ D.E. Knuth. Omicron mare și Omega mare și Theta mare : articol . - ACM Sigact News, 1976. - V. 8 , Nr. 2 . - S. 18-24 . Arhivat din original pe 15 august 2016.

Literatură

D. Green, D. Knuth. Metode matematice pentru analiza algoritmilor. — Trans. din engleza. — M .: Mir, 1987. — 120 p.
J. McConnell. Fundamentele algoritmilor moderni. - Ed. 2 suplimentare - M . : Technosfera, 2004. - 368 p. — ISBN 5-94836-005-9 .
John E. Sălbatic. Complexitatea calculelor. - M . : Factorial, 1998. - 368 p. — ISBN 5-88688-039-9 .
V. N. Krupsky. O introducere în complexitatea computațională. - M . : Presa factorială, 2006. - 128 p. — ISBN 5-88688-083-6 .
Herbert S. Wilf. Algoritmi și complexități .
Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Capitolul 3. Creșterea funcțiilor // Algoritmi: construcție și analiză = Introduction to Algorithms / Ed. I. V. Krasikova. - Ed. a II-a. - M. : Williams, 2005. - S. 87-108. — ISBN 5-8459-0857-4 .
Bugrov, Nikolsky. Matematică superioară, volumul 2.
Dionysis Zindros. Introducere în analiza complexității algoritmilor (2012). Consultat la 11 octombrie 2013. Arhivat din original pe 10 octombrie 2013. (Rusă)