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

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

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

Означення

«О» велике. Нехай задані дві комплекснозначні функції $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)| \le \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)| \le \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 \ge 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}\le 10^{m-n}$, оскільки $n \ge m$. Отже, якщо $|z|>10$, нерівність $|z|^m \le 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 \ge 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!)	факторіальне

Див. також

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