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

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

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

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

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

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

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

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

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

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

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

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