Открыть сервис
Главная → Блог → Символы Ландау

Символы Ландау

Символы Ландау — это совокупность математических обозначений (O, o, Ω, ω, Θ, ~), используемых для описания асимптотического поведения функций, то есть их роста или убывания при стремлении аргумента к некоторому пределу (чаще всего к бесконечности или к нулю). Введены немецким математиком Эдмундом Ландау в начале XX века. Широко применяются в теории алгоритмов, теории чисел, математическом анализе и других разделах математики для сравнительной оценки сложности, точности приближений и скорости сходимости.

История

Понятие асимптотического сравнения функций восходит к работам Пауля Бахмана (1894), который ввёл обозначение «O» (от нем. Ordnung — порядок). Однако систематическое использование и строгое определение этих символов дал Эдмунд Ландау в своей книге «Handbuch der Lehre von der Verteilung der Primzahlen» (1909). Ландау популяризировал «O» и «o», а также ввёл символы «Ω» и «ω». Позднее, в середине XX века, Дональд Кнут предложил стандартизировать обозначения для анализа алгоритмов, добавив символ «Θ» (тета) и уточнив определения.

Основные символы

Все символы Ландау описывают поведение функции f(x) относительно другой функции g(x) при x → a (где a — конечное число или бесконечность). Обычно предполагается, что g(x) > 0 в окрестности a (кроме, возможно, самой точки a).

O-большое (асимптотическая верхняя оценка)

Определение: f(x) = O(g(x)) при x → a, если существуют константа C > 0 и окрестность U точки a такие, что для всех x ∈ U выполняется |f(x)| ≤ C·|g(x)|.

Интуитивно: функция f растёт не быстрее, чем g с точностью до постоянного множителя. Например, 3x² + 5x = O(x²) при x → ∞, так как для x > 1 выполняется |3x² + 5x| ≤ 4x².

o-малое (строгая верхняя оценка)

Определение: f(x) = o(g(x)) при x → a, если для любого ε > 0 существует окрестность U точки a такая, что для всех x ∈ U выполняется |f(x)| ≤ ε·|g(x)|.

Это означает, что f растёт пренебрежимо медленно по сравнению с g: f(x)/g(x) → 0 при x → a. Например, x² = o(x³) при x → ∞, но x² ≠ o(x²).

Ω-большое (асимптотическая нижняя оценка)

Определение: f(x) = Ω(g(x)) при x → a, если существуют константа C > 0 и окрестность U точки a такие, что для всех x ∈ U выполняется |f(x)| ≥ C·|g(x)|.

Симметрично O-большому: f растёт не медленнее, чем g. Например, x³ = Ω(x²) при x → ∞.

ω-малое (строгая нижняя оценка)

Определение: f(x) = ω(g(x)) при x → a, если для любого C > 0 существует окрестность U точки a такая, что для всех x ∈ U выполняется |f(x)| ≥ C·|g(x)|.

Это означает, что f растёт неограниченно быстрее, чем g: f(x)/g(x) → ∞. Например, x³ = ω(x²) при x → ∞.

Θ-большое (точный порядок роста)

Определение: f(x) = Θ(g(x)) при x → a, если одновременно f(x) = O(g(x)) и f(x) = Ω(g(x)). Или, эквивалентно, существуют константы C₁, C₂ > 0 и окрестность U такие, что C₁·|g(x)| ≤ |f(x)| ≤ C₂·|g(x)| для всех x ∈ U.

Θ-оценка означает, что функции имеют одинаковый порядок роста. Например, 3x² + 5x = Θ(x²) при x → ∞.

Асимптотическая эквивалентность

Определение: f(x) ~ g(x) при x → a, если f(x)/g(x) → 1.

Это сильнее, чем Θ: не только порядок роста одинаков, но и отношение стремится к единице. Например, x² + x ~ x² при x → ∞.

Свойства и правила работы

Символы Ландау подчиняются определённым алгебраическим правилам, которые позволяют упрощать выражения:

  • Сложение: O(f) + O(g) = O(max(|f|, |g|)). Например, O(x²) + O(x) = O(x²).
  • Умножение: O(f)·O(g) = O(f·g). Например, O(x²)·O(x) = O(x³).
  • Умножение на константу: c·O(f) = O(f) для любой ненулевой константы c.
  • Транзитивность: Если f = O(g) и g = O(h), то f = O(h).
  • Симметрия для Θ: f = Θ(g) тогда и только тогда, когда g = Θ(f).

Важно: символы Ландау не являются равенствами в обычном смысле. Запись f = O(g) означает, что f принадлежит классу функций, ограниченных g с точностью до константы. Поэтому корректнее писать f ∈ O(g), но исторически сложилось использование знака равенства.

Применение

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

В информатике символы Ландау (особенно O, Ω, Θ) используются для оценки временной и пространственной сложности алгоритмов. Например:

Θ-оценка даёт точную асимптотику: например, сортировка слиянием имеет Θ(n log n) в худшем, среднем и лучшем случаях.

Теория чисел

Символы Ландау широко применяются в аналитической теории чисел для описания распределения простых чисел. Классический пример — асимптотический закон распределения простых чисел: π(x) ~ x / ln x, где π(x) — количество простых чисел, не превосходящих x. Также используются оценки остаточных членов: π(x) = x / ln x + O(x / ln² x).

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

В анализе символы o и O применяются при разложении функций в ряды Тейлора, при вычислении пределов и оценке погрешностей. Например, sin x = x - x³/6 + o(x³) при x → 0.

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

Символы Ландау не всегда удобны для точных вычислений, так как скрывают константы и младшие члены. Это может приводить к парадоксам: например, алгоритм с O(n²) может на практике работать быстрее алгоритма с O(n log n) для малых n из-за больших скрытых констант. Кроме того, при использовании нескольких символов в одном выражении (например, O(f) + O(g)) теряется информация о конкретных функциях, что требует осторожности при интерпретации.

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

  • В русскоязычной литературе символы Ландау иногда называют «асимптотическими обозначениями» или «обозначениями «O» большое».
  • В компьютерных науках часто используется только O-большое, хотя для полного анализа необходимы также Ω и Θ.
  • Символ «~» (тильда) для асимптотической эквивалентности ввёл не Ландау, а Гаусс, но он стал частью стандартного набора.

Источники

  • Ландау Э. Основы анализа. — М.: Иностранная литература, 1947.
  • Кнут Д. Искусство программирования. Том 1. Основные алгоритмы. — М.: Вильямс, 2006.
  • Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. — М.: Мир, 1998.
  • Виноградов И. М. Основы теории чисел. — М.: Наука, 1972.
  • Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979.

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →

Похожие материалы