Нотація Ландау
Матеріал з Вікіпедії — вільної енциклопедії.
Асимптотична нотація великого О, відома також як нотація Ландау - розповсюджена математична нотація для формального запису асимптотичної поведінки функцій. Широко вживається в теорії складності обчислень, інформатиці та математиці.
Названа нотацією Ландау на честь німецького математика Едмунда Ландау, який і популяризував цю нотацію.
[ред.] Позначення
Нехай задані дві числові функції 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
x0;
Часто для позначення того факту, що 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!) | факторіальне |
| Це незавершена стаття з математики. Ви можете допомогти проекту, виправивши або дописавши її. |

