Нотація Ландау

Асимптотична нотація великого О, відома також як нотація Ландау — розповсюджена математична нотація для формального запису асимптотичної поведінки функцій. Широко вживається в теорії складності обчислень, інформатиці та математиці.

Названа нотацією Ландау на честь німецького математика Едмунда Ландау, який і популяризував цю нотацію.

Означення

«О» велике. Нехай задані дві комплекснозначні функції $f(z)$ та $g(z)$ визначені в деякій множині $D$ комплексної площини. Тоді говорять, що

$f(z)\in O(g(z)),\,\,\,z\in D,$

якщо існує константа K >0, що виконується нерівність |f(z)| ≤ K |g(z)| для $z\in D$.

«O» велике в околі $z_{0}$. Нехай $f(z)$ і $g(z)$ дві комплекснозначні функції визначені в деякій множині $D$ комплексної площини, замикання якої містить точку $z_{0}$ (тобто, $z_{0}$ є граничною точкою $D$). Тоді ми пишемо

$f(z)=O(g(z))$ при $z\to z_{0}$ з $D$

якщо існує число $\delta >0$ таке, що

$f(z)=O(g(z)),\ z\in D,\ 0<|z-z_{0}|<\delta$

в сенсі означення «О» великого. Тобто, $f$ обмежена величиною добутку константи на $g$ для всіх $z$ з $D$, які лежать досить близько до $z_{0}$.

«O» велике в нескінченності. Нехай $f(z)$ і $g(z)$ дві комплекснозначні функції визначені в необмежиній множині $D$ комплексної площини. Тоді ми кажемо, що

$f(z)=O(g(z))$ при $z\to \infty$ з $D$

якщо існує число $M>0$ так що

$f(z)=O(g(z)),\ z\in D,\ |z|<M$,

в сенсі означення «О» великого. Тобто, $f$ обмежена величиною добутку деякої константи на $g$, для достатньо великих $z$ з $D$.

«o» маленьке. Нехай $f(z)$ і $g(z)$ дві комплекснозначні функції визначені в деякій множині $D$ комплексної площини замикання якої містить точку $z_{0}$. Тоді ми кажемо, що

$f(z)=o(g(z))$ при $z\to z_{0}$ з $D$

якщо для довільного $\epsilon >0$, як завгодно малого, існує відповідне йому $\delta (\epsilon )>0$, що

$|f(z)|\leq \epsilon |g(z)|$ для $z\in D$ і $0<|z-z_{0}|<\delta (\epsilon )$.

Тобто, $f$ є меншим за величиною за будь-який малий добуток $g$ для $z\in D$ досить близьких до точки $z_{0}$.

«о» маленьке в нескінченності Нехай $f(z)$ і $g(z)$ комплекснозначні функції визначені в необмеженій множині $D$ комплексної площини. Тоді ми пишемо

$f(z)=o(g(z))$ при $z\to \infty$ з $D$

якщо для довільного $\epsilon >0$, як завгодно малого, ми можемо знайти відповідне $M(\epsilon )>0$ таке що

$|f(z)|\leq \epsilon |g(z)|$ для $z\in D$ і $|z|>M(\epsilon )$.

Позначення

Функції f(x) та g(x) називають функціями одного порядку, якщо f(x) = O(g(x)) та g(x) є O(f(x)) для x $\to$ x₀;

Часто для позначення того факту, що f(x) є O(g(x)) використовується запис f(x) = O(g(x)), хоч це не зовсім правильно і в деяких випадках може привести до плутанини.

Приклад

Нехай $n$ і $m$ цілі числа. Якщо $n\geq m$, то $z^{m}=O(z^{n})$ при $z\to \infty$. Для доведення цього запишемо

$|z^{m}|=|z^{m-n}z^{n}|=|z^{m-n}|\cdot |z^{n}|=|z|^{m-n}\cdot |z^{n}|$

Покладемо $M=10$. Тоді $|z|>M$ означає що $|z|^{m-n}\leq 10^{m-n}$, оскільки $n\geq m$. Отже, якщо $|z|>10$, нерівність $|z|^{m}\leq K|z^{m-n}|$ виконується при виборі $K=10^{m-n}$. Також, з аналогічним обмеженням на $n$ та $m$, ми маємо, що $z^{n}=O(z^{m})$ при $z\to 0$ з $\mathbb {C}$. Для доведення цього запишемо

$|z^{n}|=|z^{n-m}z^{m}|=|z^{n-m}|\cdot |z^{m}|=|z|^{n-m}\cdot |z^{m}|.$

Виберемо, наприклад, $\delta =3$. Тоді, $0<|z|<3$ означає, що $|z|^{n-m}<3^{n-m}$ оскільки $n\geq m$.

Деякі важливі класи відношень

Графіки деяких поширених функцій.

Нижче наведений список класів функцій, які часто зустрічаються в аналізі алгоритмів. Тут n $\to$ ∞, с — константа. Функції, які зростають повільніше, наведені першими.

нотація	назва
O(1)	константа
O(log n)	логарифмічне
O([log n]c)	полілогарифмічне
O(n)	лінійне
O(n · log n)	лінеарітмічне
O(n2)	квадратичне
O(nc)	поліноміальне
O(cn)	експоненціальне
O(n!)	факторіальне

Див. також

• Таблиця математичних символів