ω-малое¶

ω-малое (также ω-малое, о-малое, о-малое от; обозначение: \( o(\cdot) \) или \( \omega(\cdot) \) в зависимости от контекста) — это математическое обозначение, используемое в асимптотическом анализе для описания класса функций, которые растут (или убывают) строго медленнее (или быстрее) заданной функции при стремлении аргумента к некоторому пределу (обычно к бесконечности или к нулю). В отличие от «O-большого», которое задаёт верхнюю границу роста с точностью до константы, «ω-малое» указывает на пренебрежимо малую величину по сравнению с эталоном. Термин является частью семейства символов Ландау (наряду с \( O \), \( \Omega \), \( \Theta \), \( o \), \( \omega \)), широко применяемых в теории алгоритмов, математическом анализе, теории чисел и других разделах математики.

¶Определение

Формально, пусть \( f(x) \) и \( g(x) \) — две функции, определённые на некотором множестве, и \( x \to a \), где \( a \) — конечное число или бесконечность. Говорят, что \( f(x) \) является «ω-малым» от \( g(x) \) при \( x \to a \), и пишут \( f(x) = \omega(g(x)) \), если для любого положительного числа \( C \) существует такая окрестность точки \( a \), что для всех \( x \) из этой окрестности выполняется неравенство:

\[ |f(x)| > C \cdot |g(x)| \]

Иными словами, \( f(x) \) растёт неограниченно быстрее, чем \( g(x) \), или, что эквивалентно, \( g(x) = o(f(x)) \). В русскоязычной литературе обозначение «ω-малое» часто путают с «о-малым» (обозначаемым \( o(\cdot) \)), однако в международной практике (особенно в анализе алгоритмов) символ \( \omega \) используется для строгой нижней границы, а \( o \) — для строгой верхней.

¶Различие между \( o \) и \( \omega \)

• \( o \)-малое: \( f(x) = o(g(x)) \) означает, что \( \lim_{x \to a} \frac{f(x)}{g(x)} = 0 \). Функция \( f \) пренебрежимо мала по сравнению с \( g \).
• \( \omega \)-малое: \( f(x) = \omega(g(x)) \) означает, что \( \lim_{x \to a} \frac{|f(x)|}{|g(x)|} = \infty \). Функция \( f \) доминирует над \( g \) в асимптотическом смысле.

В некоторых учебниках (например, по теории чисел) символ \( \omega \) может использоваться для обозначения «о-малого» в смысле «строго меньше», но это менее распространено.

¶История

Символы асимптотического анализа были введены немецким математиком Эдмундом Ландау в начале XX века. В своей работе по теории чисел (1909) Ландау использовал \( O \) и \( o \) для оценки остаточных членов. Позже, в 1910-х годах, Годфри Харолд Харди и Джон Идензор Литлвуд развили символику, добавив \( \Omega \) и \( \omega \) для обозначения нижних и строгих нижних границ. В современной теории алгоритмов символы \( \omega \) и \( \Omega \) стали стандартом после работ Дональда Кнута (1976), который унифицировал обозначения в книге «Искусство программирования».

¶Свойства

• Транзитивность: Если \( f = \omega(g) \) и \( g = \omega(h) \), то \( f = \omega(h) \).
• Связь с \( O \) и \( \Omega \): \( f = \omega(g) \) эквивалентно \( g = o(f) \). Также \( f = \omega(g) \) влечёт \( f = \Omega(g) \) (но не наоборот).
• Сумма и произведение: Если \( f_1 = \omega(g) \) и \( f_2 = \omega(g) \), то \( f_1 + f_2 = \omega(g) \). Если \( f = \omega(g) \) и \( h \) — положительная функция, то \( f \cdot h = \omega(g \cdot h) \).
• Несимметричность: \( f = \omega(g) \) не означает, что \( g = \omega(f) \); наоборот, \( g = o(f) \).

¶Примеры

1. Степенная функция: \( x^2 = \omega(x) \) при \( x \to \infty \), так как \( \frac{x^2}{x} = x \to \infty \).
2. Логарифм: \( \ln x = \omega(1) \) при \( x \to \infty \), но \( \ln x = o(x) \).
3. Экспонента: \( e^x = \omega(x^n) \) для любого фиксированного \( n \) при \( x \to \infty \).
4. Стремление к нулю: \( x = \omega(x^2) \) при \( x \to 0 \), так как \( \frac{x}{x^2} = \frac{1}{x} \to \infty \).

¶Применение

¶Теория алгоритмов

В анализе сложности алгоритмов «ω-малое» используется для описания строгой нижней границы времени выполнения. Например, если алгоритм сортировки имеет сложность \( \Omega(n \log n) \), то это означает, что он не может быть быстрее \( n \log n \) в худшем случае. Если же говорят, что сложность алгоритма \( \omega(n) \), это значит, что его время работы растёт строго быстрее линейной функции, то есть \( T(n) > C \cdot n \) для любого \( C \) при достаточно больших \( n \). Однако на практике чаще используют \( \Omega \) и \( \Theta \), так как \( \omega \) указывает на отсутствие константной верхней границы.

¶Математический анализ

В разложениях функций в ряды «ω-малое» применяется для обозначения остаточных членов, которые стремятся к нулю быстрее, чем эталонная функция. Например, в формуле Тейлора: \( f(x) = f(a) + f'(a)(x-a) + o(x-a) \). Здесь \( o(x-a) \) — это «о-малое», а не «ω-малое», но в некоторых контекстах (например, при оценке погрешности) используют \( \omega \) для указания, что остаток доминирует над главным членом.

¶Теория чисел

В асимптотических законах распределения простых чисел символы \( O \) и \( o \) используются для оценки остатков. Например, \( \pi(x) = \frac{x}{\ln x} + o\left(\frac{x}{\ln x}\right) \), где \( \pi(x) \) — количество простых чисел, не превосходящих \( x \). «ω-малое» здесь редкость, но может появляться при сравнении функций, растущих быстрее, чем \( \frac{x}{\ln x} \).

¶Связь с другими обозначениями

¶Критика и ограничения

• Неоднозначность в обозначениях: В некоторых учебниках (особенно советских) символ \( \omega \) не использовался, а «ω-малое» заменялось на «о-малое» с уточнением «строгое». Это может приводить к путанице при чтении современной литературы.
• Отсутствие количественной оценки: Как и другие асимптотические символы, «ω-малое» не даёт информации о константах или скорости роста, а лишь указывает на качественное соотношение.
• Применимость только к неотрицательным функциям: В большинстве определений предполагается, что функции положительны или неотрицательны в окрестности предела. Для знакопеременных функций требуется модуль.

¶Интересные факты

• В русскоязычной математической традиции (например, в работах А. Н. Колмогорова) символ \( \omega \) часто использовался для обозначения «о-малого» в смысле «строго меньше», что отличается от западной практики. Это связано с тем, что в СССР символы Ландау были адаптированы с некоторыми вариациями.
• В компьютерной науке «ω-малое» встречается реже, чем \( o \) и \( \Omega \), поскольку алгоритмы редко имеют строго растущие нижние границы без констант. Однако в теории сложности (например, в гипотезе о том, что \( P \neq NP \)) используются асимптотические обозначения для доказательства невозможности полиномиальных решений.

¶Источники

• Кнут Д. «Искусство программирования», том 1, раздел 1.2.11.1.
• Ландау Э. «Основы анализа», 1930.
• Харди Г. Х., Литлвуд Дж. И. «Некоторые проблемы теории чисел», 1914.
• Кормен Т., Лейзерсон Ч., Ривест Р. «Алгоритмы: построение и анализ», глава 3.