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

Матеріал з Вікіпедії — вільної енциклопедії.

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

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

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

Нехай задані дві числові функції f(x) та g(x). Тоді говорять, що f(x) є O(g(x)) тоді, коли виконується нерівність |f(x)| ≤ M |g(x)| для деяких x0 та М таких, що M >0 та x > x0.

Функції 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 \to ∞, с -- константа. Функції, які зростають повільніше, наведені першими.


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



Сигма Це незавершена стаття з математики.
Ви можете допомогти проекту, виправивши або дописавши її.
Іншими мовами