Оглавление
- 1 Обозначение большой буквы “О”
- 1.1 Обозначение Big O
- 1.2 Формальное определение
- 1.3 Пример использования
- 1.4 Области применения
- 1.5 Бесконечная асимптотика
- 1.6 Бесконечно малая асимптотика
- 1.7 Обозначение big O
- 1.8 Изменение единиц измерения
- 1.9 Изменение переменных
- 1.10 Умножение на константу
- 1.11 Множество переменных
- 1.12 Вопросы обозначения
- 1.13 Другие арифметические операторы
- 1.14 Многократное использование
- 1.15 Верстка
- 1.16 Порядок выполнения общих функций
- 1.17 Связанные асимптотические обозначения
- 1.18 Определение big-O и little-o
- 1.19 Примеры использования
- 1.20 Большая Омега-нотация
- 1.21 Семейство обозначений Бахмана–Ландау
- 1.22 Использование в информатике
- 1.23 Другие обозначения
- 1.24 Обобщения и связанные обычаи
- 1.25 История
- 1.26 История символов Омега и ∼
- 1.27 Популяризация символов в компьютерных науках
- 1.28 Другие символы Харди
- 1.29 Символ ≪
- 1.30 Происхождение символа “О”
- 1.31 Другие обозначения и их использование
- 1.32 Полный текст статьи:
- 2 Обозначение Big O
Обозначение большой буквы “О”
-
Обозначение Big O
- Используется для описания предельного поведения функции при стремлении аргумента к бесконечности.
- Изобретено Полом Бахманом и Эдмундом Ландау.
- Описывает верхнюю границу скорости роста функции.
-
Формальное определение
- Функция f(x) = O(g(x)) означает, что |f(x)| ≤ M|g(x)| для всех x ≥ x0.
- В информатике используется более строгое определение для функций от натуральных чисел до неотрицательных действительных чисел.
-
Пример использования
- Функция f(x) = 6×4 − 2×3 + 5 упрощается до O(x4).
- Формальное определение подтверждает это упрощение.
-
Области применения
- В математике используется для аппроксимации функций.
- В информатике применяется для анализа алгоритмов.
-
Бесконечная асимптотика
- Используется для анализа эффективности алгоритмов.
- Пример: T(n) = 4n2 − 2n + 2, где n2 доминирует при больших n.
-
Бесконечно малая асимптотика
- Используется для описания погрешности в приближении к математической функции.
- Пример: экспоненциальный ряд с O(x3) означает, что ошибка не превышает нескольких постоянных раз |x3|.
-
Обозначение big O
- Функция может быть ограничена многочленом от n, что позволяет пренебречь членами более низкого порядка при n стремящемся к бесконечности.
- Наборы O(nc) и O(cn) сильно отличаются, если c больше единицы.
- Функция, растущая быстрее, чем nc для любого c, называется суперполиномиальной.
- Функция, растущая медленнее, чем любая экспоненциальная функция вида cn, называется субэкспоненциальной.
-
Изменение единиц измерения
- Изменение единиц измерения может повлиять на порядок выполнения алгоритма.
- Изменение единиц измерения эквивалентно умножению соответствующей переменной на константу.
-
Изменение переменных
- Изменение переменных также может повлиять на порядок выполнения алгоритма.
- Например, время выполнения алгоритма может быть O(n), если измеряется как количество n цифр входного числа x, но O(log x), если измеряется как функция самого входного числа x.
-
Умножение на константу
- Если f = O(g), то k ⋅ f = O(g) для любой ненулевой константы k.
-
Множество переменных
- Большая O может использоваться с несколькими переменными.
- Определение big O для нескольких переменных требует существования констант M и C, таких что |f(x)| ≤ C|g(x)| для всех x с xi ≥ M для некоторых i.
-
Вопросы обозначения
- Утверждение “f(x) равно O[ g(x)]” обычно записывается как f(x) = O[ g(x)], что может вводить в заблуждение.
- Более точным было бы использовать обозначение множества и записывать f(x) ∈ O[ g(x)].
-
Другие арифметические операторы
- Запись с большой буквы O может использоваться в сочетании с другими арифметическими операторами.
- Пример: T(n) = 55n3 + O(n2) выражает общую временную сложность алгоритма.
-
Многократное использование
- O(·) может встречаться в разных местах уравнения, даже по нескольку раз с каждой стороны.
- Смысл таких утверждений заключается в том, что для любых функций, удовлетворяющих каждому O(·) в левой части, существуют функции, удовлетворяющие каждому O(·) в правой части.
-
Верстка
- Большая буква “О” набирается в виде выделенной курсивом заглавной буквы “O”.
- В TeX он создается простым вводом O в математическом режиме.
-
Порядок выполнения общих функций
- Функции с более медленным ростом обычно перечисляются первыми.
- Заявление f(n) = O(n!) иногда ослабляется до f(n) = O(n^n) для вывода более простых формул.
-
Связанные асимптотические обозначения
- Большая буква “О” широко используется в информатике и образует семейство обозначений Бахмана–Ландау.
- Обозначение Литтл-о означает, что g(x) значительно возрастает быстрее, чем f(x).
-
Определение big-O и little-o
- big-O: верно для одной константы M
- little-o: верно для каждой положительной константы ε
- little-o сильнее, чем big-O
-
Примеры использования
- 2×2 = O(x2), но 2×2 ≠ o(x2)
- Если g(x) не равно нулю, то f(x) = o(g(x)) эквивалентно
-
Большая Омега-нотация
- Ω: два определения, Харди–Литтлвуд и Кнут
- Харди–Литтлвуд: f(x) = Ω(g(x)) отрицает f(x) = o(g(x))
- Кнут: Ω более строгое, чем Харди–Литтлвуд
-
Семейство обозначений Бахмана–Ландау
- o, O, Θ, ∼, Ω, ω
- Информатика использует O, Θ, o, ω, Ω
- Аналитическая теория чисел использует O, o, ≍, Ω, ∼
-
Использование в информатике
- big O может использоваться для асимптотической жесткой границы
- big Theta Θ может быть более подходящим в некоторых контекстах
-
Другие обозначения
- O(g) = {f: существуют положительные константы c и n0 такие, что 0 ≤ f(n) ≤ cg(n) для всех n ≥ n0}
- Й: скрывает полилогарифмические множители
- O*: запись с большой буквы O, игнорирующая логарифмические коэффициенты
- L: функции между полиномиальными и экспоненциальными
-
Обобщения и связанные обычаи
- Обобщение на нормированные векторные пространства и топологические группы
- Обозначение o может использоваться для производных и эквивалентности функций
-
История
- Символ O введен Полом Бахманом в 1894 году
- Символ o введен Эдмундом Ландау в 1909 году
- Символ Ω введен Харди и Литтлвудом в 1914 году
-
История символов Омега и ∼
- Символы Омега и ∼ стали широко использоваться в теории чисел с 1950-х годов.
- Символ ∼ получил современное определение в 1909 году Ландау и в 1910 году Харди.
- Символ ≍ означает, что обе функции удовлетворяют условию O(g(x)) и O(f(x)).
-
Популяризация символов в компьютерных науках
- В 1970-х годах Дональд Кнут популяризировал символ “О” в компьютерных науках.
- Кнут предложил обозначение Θ(g(x)) для Харди ≍ g(x).
- Кнут также предложил другое определение для символа Омега Харди и Литтлвуда.
-
Другие символы Харди
- Харди предложил символы ≼ и ≺, но не использовал их в своих работах.
- Символы ≼ и ≺ больше не используются.
-
Символ ≪
- В 1930-х годах Иван Матвеевич Виноградов представил символ ≪, который стал часто использоваться в теории чисел.
- Символ ≪ часто используется вместе с символом “О”.
-
Происхождение символа “О”
- Символ “О” первоначально расшифровывался как “порядок” и является латинской буквой.
- Кнут позже стал рассматривать этот символ как заглавный омикрон.
-
Другие обозначения и их использование
- В статье упоминаются другие обозначения, такие как асимптотическая вычислительная сложность и асимптотическое разложение.
- Символ “О” также используется в обозначении вероятности и анализе алгоритмов.