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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

Означення[ред.ред. код]

«О» велике. Нехай задані дві комплекснозначні функції 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 x0;

Часто для позначення того факту, що 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!) факторіальне

Див. також[ред.ред. код]