Перегляд вихідного коду сторінки Нотація Ландау

[[Файл:Big-O-notation.png|300px|thumb|Приклад використання нотації О-велике: <math>{\color{red}f(x)} \in O{\color{blue}(g(x))}</math>, бо існують <math>L>0</math> (наприклад, <math>L=1</math>) та <math>x_0</math> (наприклад, <math>x_0=5</math>), такі, що <math>{\color{red}f(x)}\leqslant {\color{blue}Lg(x)}</math> для кожного <math>x\geqslant x_0</math>.]]
'''Нотація Ландау'''&nbsp;— поширена математична нотація для формального запису [[Асимптотичний аналіз|асимптотичної поведінки функцій]]. Широко вживається в [[теорія складності обчислень|теорії складності обчислень]], [[інформатика|інформатиці]] та [[математика|математиці]].

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

== Відношення «{{mvar|O}}» ==
'''Означення для функцій [[Дійсне число|дійсного]] ([[Комплексне число|комплексного]]) аргументу'''

Через <math>\mathbb{K}</math> позначимо <math>\R</math> або <math>\C</math>. Нехай <math>A \subset \mathbb{K}</math>, <math>f, g: A \to \mathbb{K}</math> і <math>x_0</math>&nbsp;&mdash; [[гранична точка]] множини <math>A</math>. Через <math>B(x_0, \delta)</math> позначимо [[Епсилон-окіл|<math>\delta</math>-окіл]] точки <math>x_0</math>.

Функція <math>f</math> називається '''підпорядкованою''' функції <math>g</math> при <math>x \to x_0</math>, якщо існують дійсні додатні числа <math>L</math> та <math>\delta</math> такі, що для довільного <math>x \in A \cap B(x_0, \delta) \setminus \{x_0\}</math> виконується нерівність <math>|f(x)| \leqslant L|g(x)|.</math>

Для <math>\mathbb{K} = \R</math> функція <math>f</math> називається '''підпорядкованою''' функції <math>g</math> при <math>x \to +\infty</math>, якщо існують дійсне додатнє число <math>L</math> і дійсне <math>C</math> такі, що для довільного <math>x \in A \cap (C, +\infty)</math> виконується нерівність <math>|f(x)| \leqslant L|g(x)|.</math>

Для <math>\mathbb{K} = \C</math> функція <math>f</math> називається '''підпорядкованою''' функції <math>g</math> при <math>x \to \infty</math>, якщо існують дійсне додатнє число <math>L</math> і дійсне <math>C</math> такі, що для довільного <math>x \in A \cap \{z \in \C \mid |z| > C\}</math> виконується нерівність <math>|f(x)| \leqslant L|g(x)|.</math>

Позначення: <math>f(x) = O(g(x))</math>, <math>x \to x_0</math> або <math>f = O(g)</math>, <math>x \to x_0</math>.

'''Означення для функцій [[Ціле число|цілого]] невід'ємного аргументу'''

Нехай <math>f, g : \N \cup \{0\} \to \R_{+}</math>. Функція <math>f</math> називається '''підпорядкованою''' функції <math>g</math> якщо існують додатнє дійсне число <math>C</math> і натуральне <math>n_0</math> такі, що для довільного <math>n \geqslant n_0</math> виконується нерівність <math>f(n) \leqslant C g(n).</math>

Позначення: <math>f(n) = O(g(n))</math> або <math>f = O(g)</math>.

Також кажуть, що «<math>f</math> зростає не швидше ніж <math>g</math>» або «<math>g</math> є '''асимптотичною верхньою оцінкою''' <math>f</math>».

=== Властивості ===
# <math>C \cdot f = O(f), x \to x_0</math> для довільного <math>C \in \mathbb{K}.</math>
# <math>C = O(1)</math> для довільного <math>C \in \mathbb{K}.</math>
# Якщо <math>\lim\limits_{x \to x_0} \left|\frac{f(x)}{g(x)}\right| \in \R</math>, то <math>f = O(g), x \to x_0.</math>
# Якщо <math>f = O(h), x \to x_0</math> і <math>g = O(h), x \to x_0</math>, то <math>f + g = O(h), x \to x_0.</math>
# Якщо <math>f = O(g), x \to x_0,</math> то <math>f + g = O(g), x \to x_0.</math>
# Якщо <math>f_1 = O(g_1), x \to x_0</math> і <math>f_2 = O(g_2), x \to x_0,</math> то <math>f_1 \cdot f_2 = O(g_1 \cdot g_2), x \to x_0.</math>
# Якщо <math>f_1 = O(g_1), x \to x_0</math> і <math>f_2 = O(g_2), x \to x_0,</math> то <math>f_1 + f_2 = O(\max(g_1, g_2)), x \to x_0.</math>
# Якщо <math>f = O(g), x \to x_0</math> і <math>g = O(h), x \to x_0,</math> то <math>f = O(h), x \to x_0.</math> ([[транзитивність]])

== Відношення «{{mvar|Ω}}» ==
'''Означення для функцій дійсного (комплексного) аргументу'''

Через <math>\mathbb{K}</math> позначимо <math>\R</math> або <math>\C</math>. Нехай <math>A \subset \mathbb{K}</math>, <math>f, g: A \to \mathbb{K}</math> і <math>x_0</math>&nbsp;&mdash; гранична точка множини <math>A</math>. Через <math>B(x_0, \delta)</math> позначимо [[Епсилон-окіл|<math>\delta</math>-окіл]] точки <math>x_0</math>.

Кажуть, що функція <math>f</math> '''підпорядковує''' функцію <math>g</math> при <math>x \to x_0</math>, якщо існують дійсні додатні числа <math>L</math> та <math>\delta</math> такі, що для довільного <math>x \in A \cap B(x_0, \delta) \setminus \{x_0\}</math> виконується нерівність <math>|f(x)| \geqslant L|g(x)|.</math>

Для <math>\mathbb{K} = \R</math> кажуть, що функція <math>f</math> '''підпорядковує''' функцію <math>g</math> при <math>x \to +\infty</math>, якщо існують дійсне додатнє число <math>L</math> і дійсне <math>C</math> такі, що для довільного <math>x \in A \cap (C, +\infty)</math> виконується нерівність <math>|f(x)| \geqslant L|g(x)|.</math>

Для <math>\mathbb{K} = \C</math> кажуть, що функція <math>f</math> '''підпорядковує''' функцію <math>g</math> при <math>x \to \infty</math>, якщо існують дійсне додатнє число <math>L</math> і дійсне <math>C</math> такі, що для довільного <math>x \in A \cap \{z \in \C \mid |z| > C\}</math> виконується нерівність <math>|f(x)| \geqslant L|g(x)|.</math>

Позначення: <math>f(x) = \Omega(g(x))</math>, <math>x \to x_0</math> або <math>f = \Omega(g)</math>, <math>x \to x_0</math>.

'''Означення для функцій цілого невід'ємного аргументу'''

Нехай <math>f, g : \N \cup \{0\} \to \R_{+}</math>. Кажуть, що функція <math>f</math> '''підпорядковує''' функцію <math>g</math> якщо існують додатнє дійсне число <math>C</math> і натуральне <math>n_0</math> такі, що для довільного <math>n \geqslant n_0</math> виконується нерівність <math>f(n) \geqslant C g(n).</math>

Позначення: <math>f(n) = \Omega(g(n))</math> або <math>f = \Omega(g)</math>.

Також кажуть, що «<math>f</math> зростає не повільніше ніж <math>g</math>» або «<math>g</math> є '''асимптотичною нижньою оцінкою''' <math>f</math>».

=== Властивості ===
# <math>g = O(f), x \to x_0</math> [[тоді й лише тоді]], коли <math>f = \Omega(g), x \to x_0.</math>
# <math>C \cdot f = \Omega(f), x \to x_0</math> для довільного <math>C \in \mathbb{K}\setminus \{0\}.</math>
# <math>C = \Omega(1)</math> для довільного <math>C \in \mathbb{K}\setminus \{0\}.</math>
# Якщо <math>\lim\limits_{x \to x_0} \left|\frac{g(x)}{f(x)}\right| \in \R</math>, то <math>f = \Omega(g), x \to x_0.</math>
# Якщо <math>f = \Omega(h), x \to x_0</math> і <math>g = \Omega(h), x \to x_0</math>, то <math>f + g = \Omega(h), x \to x_0.</math>
# Якщо <math>f = \Omega(g), x \to x_0,</math> то <math>f + g = \Omega(g), x \to x_0.</math>
# Якщо <math>f_1 = \Omega(g_1), x \to x_0</math> і <math>f_2 = \Omega(g_2), x \to x_0,</math> то <math>f_1 \cdot f_2 = \Omega(g_1 \cdot g_2), x \to x_0.</math>
# Якщо <math>f_1 = \Omega(g_1), x \to x_0</math> і <math>f_2 = \Omega(g_2), x \to x_0,</math> то <math>|f_1| + |f_2| = \Omega(\min(g_1, g_2)), x \to x_0.</math>
# Якщо <math>f = \Omega(g), x \to x_0</math> і <math>g = \Omega(h), x \to x_0,</math> то <math>f = \Omega(h), x \to x_0.</math> ([[транзитивність]])

== Відношення «{{mvar|Θ}}» ==
'''Означення для функцій дійсного (комплексного) аргументу'''

Через <math>\mathbb{K}</math> позначимо <math>\R</math> або <math>\C</math>. Нехай <math>A \subset \mathbb{K}</math>, <math>f, g: A \to \mathbb{K}</math> і <math>x_0</math>&nbsp;&mdash; [[гранична точка]] множини <math>A</math>. Через <math>B(x_0, \delta)</math> позначимо [[Епсилон-окіл|<math>\delta</math>-окіл]] точки <math>x_0</math>.

Функція <math>g</math> називається '''асимптотичною точною оцінкою''' функції <math>f</math> при <math>x \to x_0</math>, якщо існують дійсні додатні числа <math>L_1,</math> <math>L_2</math> та <math>\delta</math> такі, що для довільного <math>x \in A \cap B(x_0, \delta) \setminus \{x_0\}</math> виконується нерівність <math>L_1|g(x)| \leqslant |f(x)| \leqslant L_2|g(x)|.</math>

Для <math>\mathbb{K} = \R</math> функція <math>g</math> називається '''асимптотичною точною оцінкою''' функції <math>f</math> при <math>x \to +\infty</math>, якщо існують дійсні додатні числа <math>L_1,</math> <math>L_2</math> і дійсне <math>C</math> такі, що для довільного <math>x \in A \cap (C, +\infty)</math> виконується нерівність <math>L_1|g(x)| \leqslant |f(x)| \leqslant L_2|g(x)|.</math>

Для <math>\mathbb{K} = \C</math> функція <math>g</math> називається '''асимптотичною точною оцінкою''' функції <math>f</math> при <math>x \to \infty</math>, якщо існують дійсні додатні числа <math>L_1,</math> <math>L_2</math> і дійсне <math>C</math> такі, що для довільного <math>x \in A \cap \{z \in \C \mid |z| > C\}</math> виконується нерівність <math>L_1|g(x)| \leqslant |f(x)| \leqslant L_2|g(x)|.</math>

Позначення: <math>f(x) = \Theta(g(x))</math>, <math>x \to x_0</math> або <math>f = \Theta(g)</math>, <math>x \to x_0</math>.

'''Означення для функцій цілого невід'ємного аргументу'''

Нехай <math>f, g : \N \cup \{0\} \to \R_{+}</math>. Функція <math>g</math> називається '''асимптотичною точною оцінкою''' функції <math>f</math> якщо існують дійсні додатні числа <math>C_1,</math> <math>C_2</math> і натуральне <math>n_0</math> такі, що для довільного <math>n \geqslant n_0</math> виконується нерівність <math>C_1 g(n) \leqslant f(n) \leqslant C_2 g(n).</math>

Позначення: <math>f(n) = \Theta(g(n))</math> або <math>f = \Theta(g)</math>.
=== Властивості ===
# <math>f = \Theta(g), x \to x_0</math> [[тоді й лише тоді]], коли <math>f = O(g), x \to x_0</math> і <math>g = \Omega(f), x \to x_0.</math>
# <math>f = \Theta(g), x \to x_0</math> тоді й лише тоді, коли <math>g = \Theta(f), x \to x_0.</math>

== Відношення «{{mvar|o}}» ==
'''Означення для функцій дійсного (комплексного) аргументу'''

Через <math>\mathbb{K}</math> позначимо <math>\R</math> або <math>\C</math>. Нехай <math>A \subset \mathbb{K}</math>, <math>f, g: A \to \mathbb{K}</math> і <math>x_0</math>&nbsp;&mdash; [[гранична точка]] множини <math>A</math>. Через <math>B(x_0, \delta)</math> позначимо [[Епсилон-окіл|<math>\delta</math>-окіл]] точки <math>x_0</math>.

Функція <math>f</math> називається '''знехтуваною''' у порівнянні з функцією <math>g</math> при <math>x \to x_0,</math> якщо для довільного додатнього <math>\varepsilon</math> існує додатнє <math>\delta</math> таке, що для довільного <math>x \in A \cap B(x_0, \delta) \setminus \{x_0\}</math> виконується нерівність <math>|f(x)| \leqslant \varepsilon |g(x)|.</math>

Для <math>\mathbb{K} = \R</math> функція <math>f</math> називається '''знехтуваною''' у порівнянні з функцією <math>g</math> при <math>x \to +\infty</math>, якщо для довільного додатнього <math>\varepsilon</math> існує додатнє <math>C</math> таке, що для довільного <math>x \in A \cap (C, +\infty)</math> виконується нерівність <math>|f(x)| \leqslant \varepsilon |g(x)|.</math>

Для <math>\mathbb{K} = \C</math> функція <math>f</math> називається '''знехтуваною''' у порівнянні з функцією <math>g</math> при <math>x \to \infty</math>, якщо для довільного додатнього <math>\varepsilon</math> існує додатнє <math>C</math> таке, що для довільного <math>x \in A \cap \{z \in \C \mid |z| > C\}</math> виконується нерівність <math>|f(x)| \leqslant \varepsilon |g(x)|.</math>

Позначення: <math>f(x) = o(g(x))</math> або <math>f = o(g).</math>

'''Означення для функцій цілого невід'ємного аргументу'''

Нехай <math>f, g : \N \cup \{0\} \to \R_{+}</math>. Функція <math>f</math> називається '''знехтуваною''' у порівнянні з функцією <math>g</math>, якщо для довільного додатнього <math>C</math> існує натуральне <math>n_0</math> таке, що для довільного <math>n \geqslant n_0</math> виконується нерівність <math>f(n) \leqslant C g(n).</math>

=== Властивості ===
# <math>f = o(g), x \to x_0</math> тоді й лише тоді, коли <math>\lim\limits_{x \to x_0} \frac{f(x)}{g(x)} = 0.</math>
# Якщо <math>f = o(g), x \to x_0,</math> то <math>f = O(g), x \to x_0.</math>
# Якщо <math>f = o(g), x \to x_0</math> і <math>g = O(h), x \to x_0,</math> то <math>f = o(h), x \to x_0.</math> Таким чином, <math>o(O(h)) = o(h), x \to x_0.</math> Аналогічно <math>O(o(h)) = o(h), x \to x_0.</math>
# Якщо <math>f_1 = o(g), x \to x_0</math> і <math>f_2 = o(g), x \to x_0,</math> то <math>f_1 + f_2 = o(g), x \to x_0.</math>
# Якщо <math>f_1 = o(g_1), x \to x_0</math> і <math>f_2 = O(g_2), x \to x_0,</math> то <math>f_1 \cdot f_2 = o(g_1 \cdot g_2), x \to x_0.</math>
# Якщо <math>f = o(g), x \to x_0</math> і <math>g = o(h), x \to x_0,</math> то <math>f = o(h), x \to x_0.</math> (транзитивність)

== Відношення «ω» ==
'''Означення для функцій дійсного (комплексного) аргументу'''

Через <math>\mathbb{K}</math> позначимо <math>\R</math> або <math>\C</math>. Нехай <math>A \subset \mathbb{K}</math>, <math>f, g: A \to \mathbb{K}</math> і <math>x_0</math>&nbsp;&mdash; [[гранична точка]] множини <math>A</math>. Через <math>B(x_0, \delta)</math> позначимо [[Епсилон-окіл|<math>\delta</math>-окіл]] точки <math>x_0</math>.

Функція <math>f</math> називається '''домінуючою''' у порівнянні з функцією <math>g</math> при <math>x \to x_0,</math> якщо для довільного додатнього <math>\varepsilon</math> існує додатнє <math>\delta</math> таке, що для довільного <math>x \in A \cap B(x_0, \delta) \setminus \{x_0\}</math> виконується нерівність <math>|f(x)| \geqslant \varepsilon |g(x)|.</math>

Для <math>\mathbb{K} = \R</math> функція <math>f</math> називається '''домінуючою''' у порівнянні з функцією <math>g</math> при <math>x \to +\infty</math>, якщо для довільного додатнього <math>\varepsilon</math> існує додатнє <math>C</math> таке, що для довільного <math>x \in A \cap (C, +\infty)</math> виконується нерівність <math>|f(x)| \geqslant \varepsilon |g(x)|.</math>

Для <math>\mathbb{K} = \C</math> функція <math>f</math> називається '''домінуючою''' у порівнянні з функцією <math>g</math> при <math>x \to \infty</math>, якщо для довільного додатнього <math>\varepsilon</math> існує додатнє <math>C</math> таке, що для довільного <math>x \in A \cap \{z \in \C \mid |z| > C\}</math> виконується нерівність <math>|f(x)| \geqslant \varepsilon |g(x)|.</math>

Позначення: <math>f(x) = \omega(g(x))</math> або <math>f = \omega(g).</math>

'''Означення для функцій цілого невід'ємного аргументу'''

Нехай <math>f, g : \N \cup \{0\} \to \R_{+}</math>. Функція <math>f</math> називається '''домінуючою''' у порівнянні з функцією <math>g</math>, якщо для довільного додатнього <math>C</math> існує натуральне <math>n_0</math> таке, що для довільного <math>n \geqslant n_0</math> виконується нерівність <math>f(n) \geqslant C g(n).</math>

=== Властивості ===
# <math>g = o(f), x \to x_0</math> тоді й лише тоді, коли <math>f = \omega(g), x \to x_0.</math>
# <math>f = \omega(g), x \to x_0</math> тоді й лише тоді, коли <math>\lim\limits_{x \to x_0} \left|\frac{f(x)}{g(x)}\right| = +\infty.</math>
# Якщо <math>f = \omega(g), x \to x_0,</math> то <math>f = \Omega(g), x \to x_0.</math>
# Якщо <math>f = \omega(g), x \to x_0</math> і <math>g = \Omega(h), x \to x_0,</math> то <math>f = \omega(h), x \to x_0.</math> Таким чином, <math>\omega(\Omega(h)) = \omega(h), x \to x_0.</math> Аналогічно <math>\Omega(\omega(h)) = \omega(h), x \to x_0.</math>
# Якщо <math>f_1 = \omega(g), x \to x_0</math> і <math>f_2 = \omega(g), x \to x_0,</math> то <math>f_1 + f_2 = \omega(g), x \to x_0.</math>
# Якщо <math>f_1 = \omega(g_1), x \to x_0</math> і <math>f_2 = \Omega(g_2), x \to x_0,</math> то <math>f_1 \cdot f_2 = \omega(g_1 \cdot g_2), x \to x_0.</math>
# Якщо <math>f = \omega(g), x \to x_0</math> і <math>g = \omega(h), x \to x_0,</math> то <math>f = \omega(h), x \to x_0.</math> (транзитивність)

== Відношення еквівалентності функцій ==
Через <math>\mathbb{K}</math> позначимо <math>\R</math> або <math>\C</math>. Нехай <math>A \subset \mathbb{K}</math>, <math>f, g: A \to \mathbb{K}</math> і <math>x_0</math>&nbsp;&mdash; гранична точка множини <math>A</math>.

Функції <math>f</math> і <math>g</math> називаються '''еквівалентними''' при <math>x \to x_0,</math> якщо <math>f - g = o(f), x \to x_0.</math>

Означення для функцій цілого невід'ємного аргументу аналогічне.

Позначення: <math>f(x) \sim g(x), x \to x_0</math> або <math>f \sim g, x \to x_0.</math>

=== Властивості ===
# Відношення <math>\sim</math> є [[Відношення еквівалентності|відношенням еквівалентності]] на множині функцій.
# Нехай для всіх <math>x \in A \setminus \{x_0\}</math> <math>g(x) \ne 0.</math> Тоді <math>f \sim g, x \to x_0</math> тоді й лише тоді, коли <math>\lim\limits_{x \to x_0} \frac{f(x)}{g(x)} = 1.</math>
# Якщо <math>f_1 \sim g_1, x \to x_0</math> і <math>f_2 \sim g_2, x \to x_0,</math> то <math>f_1 \cdot f_2 \sim g_1 \cdot g_2, x \to x_0.</math>
# Нехай для всіх <math>x \in A \setminus \{x_0\}\,</math> <math>f(x) \ne 0</math>, <math>g(x) \ne 0</math> і <math>f \sim g, x \to x_0.</math> Тоді для будь-якої функції <math>h:\, A \to \mathbb{K}</math> з існування однієї з границь
{{center|<math>\lim_{x \to x_0}(f(x) \cdot h(x))</math>, <math>\lim_{x \to x_0}(g(x) \cdot h(x))</math>}}
:: випливає існування другої границі і їх рівність.

:: Аналогічно з існування однієї з границь
{{center|<math>\lim_{x \to x_0}\frac{f(x)}{h(x)}</math>, <math>\lim_{x \to x_0}\frac{g(x)}{h(x)}</math>}}
:: випливає існування другої і їх рівність.

== Приклади ==
'''Приклад 1:''' Нехай <math>f(x) = 2 x^5 - 6 x^2 - 15</math>, <math>x \in \R</math> і <math>x_0 = +\infty</math>. Маємо:
:<math>\begin{align}
|2 x^5 - 6 x^2 - 15| &\leqslant 2|x^5| + 6 x^2 + 15\\
                  &\leqslant 15|x^5| + 15|x^5| + 15|x^5|\\
                  &= 45|x^5|,
\end{align}</math>
тобто <math>L = 45</math> і ця нерівність виконується для всіх <math>x \in (1, +\infty).</math>

Звідси <math>f(x) = O(x^5), x \to +\infty.</math>

:<math>|2 x^5 - 6 x^2 - 15| \geqslant 2|x^5|</math>, тут <math>L = 2</math> і <math>x \in (2.2, +\infty).</math> Звідси <math>f(x) = \Omega(x^5), x \to +\infty.</math>

Отже, <math>f(x) = \Theta(x^5), x \to +\infty.</math>

'''Приклад 2:''' Нехай <math> n </math> і <math> m </math> цілі числа, <math>z \in \C</math>. Якщо <math> n \geqslant m </math>, то <math> z^m=O(z^n) </math> при <math> z \to \infty</math>. Для доведення цього запишемо
{{center|
<math> |z^m|=|z^{m-n} z^n|=|z^{m-n}| \cdot|z^n|=|z|^{m-n} \cdot|z^n|</math>
}}
Покладемо <math>\delta=10</math>. Тоді <math>|z|>\delta</math> означає що <math> |z|^{m-n}\leqslant 10^{m-n} </math>, оскільки <math>n \geqslant m</math>. Отже, якщо <math>|z|>10</math>, нерівність <math> |z|^m \leqslant L|z^{m-n}| </math> виконується при виборі <math>L=10^{m-n} </math>. Також, з аналогічним обмеженням на <math>n</math> та <math>m</math>, ми маємо, що
<math> z^n=O(z^m) </math> при <math> z \to 0 </math> з <math> \mathbb{C} </math>.
Для доведення цього запишемо
{{center|
<math> |z^n|=|z^{n-m} z^m|=|z^{n-m}| \cdot|z^m|=|z|^{n-m} \cdot|z^m|.</math>
}}
Виберемо, наприклад, <math> \delta=3</math>. Тоді,
<math>0<|z|<3</math>
означає, що
<math>|z|^{n-m}<3^{n-m}</math>
оскільки
<math>n \geqslant m</math>.
== Використання ==
Нотація Ландау має дві основні сфери використання:
* У [[Математичний аналіз|математичному аналізі]] зазвичай використовується для опису того, наскільки часткова сума [[Ряд (математика)|ряду]] наближає задану функцію, наприклад, у [[Ряд Тейлора#Формула Тейлора|формулі Тейлора]] та [[Асимптотичний розклад|асимптотичному розкладі]]
* В [[Інформатика|інформатиці]] використовується для [[Обчислювальна складність|аналізу]] [[алгоритм]]ів та їх класифікації

В обох випадках функція <math>g(x)</math> в позначеннях, як правило, вибирається максимально простою без константних множників.

=== Деякі важливі класи відношень ===
{{Main|Часова складність#Таблиця типових часових складностей}}
[[Файл:Нотация Ландау.svg|thumb|300px|Графіки деяких поширених функцій.]]

Нижче наведений список класів функцій, які часто зустрічаються в аналізі алгоритмів. Тут ''с''&nbsp;&mdash; додатна константа, ''n'' необмежено зростає. Функції, які зростають повільніше, наведені першими.

{| class="wikitable" border="1" cellpadding="4" cellspacing="0"
!Нотація
!Назва
!Приклад
|-
|<math>\Theta(1)</math>
||сталий час
||Визначенно парності числа (у двійковому запису); Пошук у [[Геш-таблиця|хеш-таблиці]]
|-
|<math>\Theta(\log\log n)</math>
||двічі логарифмічний
||Час амортизації на одну операцію при використанні обмеженої [[Черга з пріоритетом|черги з пріоритетом]]<ref>{{Cite journal|first1=Kurt |last1=Mehlhorn |first2=Stefan |last2=Naher|year=1990|title=Bounded ordered dictionaries in O(log log N) time and O(n) space|journal=Information Processing Letters|doi=10.1016/0020-0190(90)90022-P|volume=35|issue=4|pages=183–189}}</ref>
|-
|<math>\Theta(\log n)</math>
||логарифмічний час
||[[Двійковий пошук]]; [[Швидке піднесення до степеня]]
|-
|<math>\Theta((\log n)^{c})</math><br /><math display=inline> c > 1</math>
||полілогарифмічний час
||
|-
|<math>\Theta(n)</math>
||лінійний час
||Пошук найбільшого або найменшого елементу невпорядкованого [[Масив (структура даних)|масиву]]
|-
|<math>\Theta(n \log n) = \Theta(\log n!)</math>
||лінеаритмічний час
||[[Швидке сортування]]; [[Сортування злиттям]]
|-
|<math>\Theta(n^2)</math>
||[[Квадратичне зростання|квадратичний]] час
||[[Сортування бульбашкою]]; [[Сортування включенням]]
|-
|<math>\Theta(n^c)</math>
||поліноміальний час
||[[Алгоритм Кармаркара]] для [[Лінійне програмування|лінійного програмування]]; [[Тест простоти AKS]]
|-
|<math>\Theta(c^n)</math><br /><math display=inline> c > 1</math>
||експоненціальний час
||Вирішення [[Задача комівояжера|задачі комівояжера]] за допомогою [[Динамічне програмування|динамічного програмування]]
|-
|<math>\Theta(n!)</math>
||факторіальний час
||Вирішення [[Задача комівояжера|задачі комівояжера]] [[Метод «грубої сили»|повним перебором]]
|}

== Розширення нотації Ландау ==
У інформатиці іноді використовується позначення Õ (читається як ''м’яке О''): ''f''(''n'')&nbsp;=&nbsp;''Õ''(''g''(''n'')) це скороченням до {{nowrap|1=''f''(''n'') = ''O''(''g''(''n'') log<sup>''k''</sup> ''n'')}} для деякого ''k''.<ref>{{Cite book|title=Introduction to algorithms|url=https://archive.org/details/introductiontoal00corm_805|url-access=limited|date=2009|publisher=MIT Press|others=Cormen, Thomas H.|isbn=978-0-262-27083-0|edition=Third|location=Cambridge, Mass.|oclc=676697295|page=[https://archive.org/details/introductiontoal00corm_805/page/n83 63]}}</ref> Іноді для цього використовують O<sup>*</sup>.<ref>{{cite journal | url=https://www.cs.helsinki.fi/u/mkhkoivi/publications/sicomp-2009.pdf | author=Andreas Björklund and Thore Husfeldt and Mikko Koivisto | title=Set partitioning via inclusion-exclusion | journal=SIAM Journal on Computing | volume=39 | number=2 | pages=546&ndash;563 | year=2009 }} Див. розділ 2.3, с.551.</ref> По суті, це нотація великого O, яка ігнорує логарифмічні множники, оскільки на швидкість зростання деякі більші функції від великих вхідних параметрів впливають значно більше, що важливіше для прогнозування поганої продуктивності під час виконання. Це позначення часто використовується, щоб уникнути «придирок» до темпів зростання, які вважаються жорстко обмеженими (log<sup>''k''</sup>&nbsp;''n'' завжди є ''o''(''n''<sup>ε</sup>) для будь-якої константи ''k'' і будь-якого {{nowrap|''ε'' > 0}}).

Для позначення функцій, які мають час зростання, що залежить від <math>\ln n</math>, між поліноміальним та експоненціальним, використовують [[L-нотація|L-нотацію]]:
:<math>L_n[\alpha,c]=e^{(c+o(1))(\ln n)^\alpha(\ln\ln n)^{1-\alpha}},</math>
де <math>c</math>&nbsp;&mdash; додатня стала, <math>\alpha \in [0, 1].</math>

== Узагальнення для функцій багатьох змінних ==
Існує декілька узагальнень нотації Ландау для функцій багатьох функцій.<ref>{{cite web |last1=Howell |first1=Rodney |title=On Asymptotic Notation with Multiple Variables |year=2008 |url=https://people.cs.ksu.edu/~rhowell/asymptotic.pdf}}</ref><ref>{{cite web |last1=Guéneau |first1=Armaël |last2=Charguéraud | first2=Arthur |last3=François |first3=Pottier |title=A Fistful of Dollars: Formalizing Asymptotic Complexity Claims via Deductive Program Verification|year=2018 |url=https://www.researchgate.net/publication/324519566_A_Fistful_of_Dollars_Formalizing_Asymptotic_Complexity_Claims_via_Deductive_Program_Verification}}</ref> Одне з них:

Для функції <math>h:\,\N_{0}^{m} \to \R_{+}</math>, де <math>\N_{0} = \N \cup \{0\}</math>, позначимо
{{center|<math>\hat{h}(n_1, \dots, n_m) = \max\{h(i_1, \dots, i_m) \mid 0 \leqslant i_j \leqslant n_j</math> для всіх <math>1 \leqslant j \leqslant m\}.</math>}}

Нехай <math>f, g : \N_{0}^{m} \to \R_{+}</math>. Функція <math>f</math> називається '''підпорядкованою''' функції <math>g</math> якщо існують додатнє дійсне число <math>C</math> і натуральне <math>n_0</math> такі, що для всіх <math>n_1 \geqslant n_0, \dots, n_m \geqslant n_0</math> виконуються нерівності 
{{center|<math>f(n_1, \dots, n_m) \leqslant C g(n_1, \dots, n_m)</math>}}
та
{{center|<math>\hat{f}(n_1, \dots, n_m) \leqslant C \hat{g}(n_1, \dots, n_m).</math>}}

Позначення: <math>f(n_1, \dots, n_m) = \hat{O}(g(n_1, \dots, n_m))</math> або <math>f = \hat{O}(g)</math>.

Аналогічно, <math>f(n_1, \dots, n_m) = \hat{\Omega}(g(n_1, \dots, n_m))</math>, якщо існують додатнє дійсне число <math>C</math> і натуральне <math>n_0</math> такі, що для всіх <math>n_1 \geqslant n_0, \dots, n_m \geqslant n_0</math> виконуються нерівності 
{{center|<math>f(n_1, \dots, n_m) \geqslant C g(n_1, \dots, n_m)</math>}}
та
{{center|<math>\hat{f}(n_1, \dots, n_m) \geqslant C \hat{g}(n_1, \dots, n_m);</math>}}

<math>f(n_1, \dots, n_m) = \hat{\Theta}(g(n_1, \dots, n_m))</math>, якщо існують додатні дійсні числа <math>C_1</math>, <math>C_2</math> і натуральне число <math>n_0</math> такі, що для всіх <math>n_1 \geqslant n_0, \dots, n_m \geqslant n_0</math> виконуються нерівності 
{{center|<math>C_1 g(n_1, \dots, n_m) \leqslant f(n_1, \dots, n_m) \leqslant C_2 g(n_1, \dots, n_m)</math>}}
та
{{center|<math>C_1 \hat{g}(n_1, \dots, n_m) \leqslant \hat{f}(n_1, \dots, n_m) \leqslant C_2 \hat{g}(n_1, \dots, n_m).</math>}}

Для функцій одного аргументу матимемо, що для <math>f(n) \ne 0</math> при деякому <math>n \in \N</math> буде <math>O(f(n)) = \hat{O}(f(n))</math>, <math>\Omega(f(n)) = \hat{\Omega}(f(n))</math> і <math>\Theta(f(n)) = \hat{\Theta}(f(n)).</math> Однак, для <math>f(n) = 0</math> при всіх <math>n \in \N</math> це не буде вірним.


<math>f(n_1, \dots, n_m) = \hat{o}(g(n_1, \dots, n_m))</math>, якщо для кожного додатного дійсного числа <math>C</math> існує натуральне число <math>n_0</math> таке, що для всіх <math>n_1 \geqslant n_0, \dots, n_m \geqslant n_0</math> виконуються нерівності 
{{center|<math>f(n_1, \dots, n_m) \leqslant C g(n_1, \dots, n_m)</math>}}
та
{{center|<math>\hat{f}(n_1, \dots, n_m) \leqslant C \hat{g}(n_1, \dots, n_m);</math>}}

<math>f(n_1, \dots, n_m) = \hat{\omega}(g(n_1, \dots, n_m))</math>, якщо для кожного додатного дійсного числа <math>C</math> існує натуральне число <math>n_0</math> таке, що для всіх <math>n_1 \geqslant n_0, \dots, n_m \geqslant n_0</math> виконуються нерівності 
{{center|<math>f(n_1, \dots, n_m) \geqslant C g(n_1, \dots, n_m)</math>}}
та
{{center|<math>\hat{f}(n_1, \dots, n_m) \geqslant C \hat{g}(n_1, \dots, n_m).</math>}}

Для функцій однієї змінної відношення <math>\hat{o}</math>, <math>\hat{\omega}</math> збігаються з відношеннями <math>o</math>, <math>\omega</math> відповідно.

Додаткова умова до <math>\hat{f}</math> і <math>\hat{g}</math> дозволяє зберегти деякі корисні властивості.

=== Властивості ===
# Для довільного <math>C > 0</math> буде <math>C f(n_1, \dots, n_m) = \hat{O}(f(n_1, \dots, n_m)).</math>
# Якщо <math>f_1 = \hat{O}(g_1)</math> і <math>f_2 = \hat{O}(g_2),</math> то <math>f_1 + f_2 = \hat{O}(\max(g_1, g_2)).</math>
# Якщо <math>g_1</math> не спадає по всім аргументам і <math>g_1(n_1, \dots, n_m) \leqslant g_2(n_1, \dots, n_m)</math> при <math>n_1 \geqslant n_0, \dots, n_m \geqslant n_0</math> для деякого <math>n_0 \in \N,</math> то з того, що <math>f = \hat{O}(g_1)</math> випливає, що <math>f = \hat{O}(g_2).</math>
# Якщо <math>g_1</math> та <math>g_2</math> не спадають по всім аргументам, то з того, що <math>f_1 = \hat{O}(g_1)</math> та <math>f_2 = \hat{O}(g_2)</math> випливає, що <math>f_1 \cdot f_2 = \hat{O}(g_1 \cdot g_2).</math>

== Див. також ==
{{Портал|Математика}}
* [[Таблиця математичних символів]]
* [[Майстер-метод|Основна теорема про рекурентні співідношення]]
* [[Обчислювальна складність]]

== Література ==
* {{Дороговцев.Математичний аналіз.ч1}}
* {{Фіхтенгольц.укр}}
*{{книга
 |автор          = John M. Howie
 |заголовок      = Complex Analysis
 |видавництво    = Springer London
 |рік            = 2003
 |сторінок       = 260
 |isbn           = 978-1-4471-0027-0
 |doi            = https://doi.org/10.1007/978-1-4471-0027-0
}}
*{{cite book | first=G. H. | last=Hardy | author-link=Ґодфрі Гарольд Гарді | title=Orders of Infinity: The 'Infinitärcalcül' of Paul du Bois-Reymond | date=1910 | url=https://archive.org/details/ordersofinfinity00harduoft | publisher=[[Cambridge University Press]]}}
*{{cite book | first=Donald | last=Knuth | author-link=Donald Knuth | title=Fundamental Algorithms | volume=1 | series=The Art of Computer Programming | edition=3-тє | publisher=Addison-Wesley | date=1997 | isbn=978-0-201-89683-1}}
*{{cite book | first1=Thomas H. | last1=Cormen | author-link1=Thomas H. Cormen | first2=Charles E. | last2=Leiserson | author-link2=Чарльз Лейзерсон | first3=Ronald L. | last3=Rivest | author-link3=Ronald L. Rivest | first4=Clifford | last4=Stein | author-link4=Кліфорд Стайн | title=Introduction to Algorithms | edition=2-ге | publisher=MIT Press and McGraw-Hill | date=2001 | isbn=978-0-262-03293-3 | title-link=Вступ до алгоритмів }}
*{{cite book | first=Michael | last=Sipser | year = 1997 | title = Introduction to the Theory of Computation | url=https://archive.org/details/introductiontoth00sips_928 | url-access=limited | publisher = PWS Publishing | isbn = 978-0-534-94728-6 | pages=[https://archive.org/details/introductiontoth00sips_928/page/n239 226]–228}}

== Примітки ==
{{Reflist}}

[[Категорія:Математична нотація]]
[[Категорія:Математичний аналіз]]
[[Категорія:Асимптотичний аналіз]]
[[Категорія:Аналіз алгоритмів]]