«O» большое и «o» малое

Поделись знанием:
Перейти к: навигация, поиск

«O» большое и «o» малое (<math>O</math> и <math>o</math>) — математические обозначения для сравнения асимптотического поведения (асимптотики) функций. Используются в различных разделах математики, но активнее всего — в математическом анализе, теории чисел и комбинаторике, а также в информатике и теории алгоритмов. Под асимптотикой понимается характер изменения функции при её стремлении к определённой точке.

<math>o(f)</math>, «о малое от <math>f</math>» обозначает «бесконечно малое относительно <math>f</math>»[1], пренебрежимо малую величину при рассмотрении <math>f</math>. Смысл термина «О большое» зависит от его области применения, но всегда <math>O(f)</math> растёт не быстрее, чем <math>f</math> (точные определения приведены ниже).

В частности:

  • фраза «сложность алгоритма есть <math>O(f(n))</math>» означает, что с увеличением параметра <math>n</math>, характеризующего количество входной информации алгоритма, время работы алгоритма будет возрастать не быстрее, чем некоторая константа, умноженная на <math>f(n)</math>;
  • фраза «функция <math>f(x)</math> является „о“ малым от функции <math>g(x)</math> в окрестности точки <math>p</math>» означает, что с приближением <math>x</math> к <math>p</math> <math>f(x)</math> уменьшается быстрее, чем <math>g(x)</math> (отношение <math>\left |f(x)\right |/\left |g(x)\right |</math> стремится к нулю).




Определения

Пусть <math>f(x)</math> и <math>g(x)</math> — две функции, определенные в некоторой проколотой окрестности точки <math>x_0</math>, причем в этой окрестности <math>g</math> не обращается в ноль. Говорят, что:

  • <math>f</math> является «O» большим от <math>g</math> при <math>x\to x_0</math>, если существует такая константа <math>C>0</math>, что для всех <math>x</math> из некоторой окрестности точки <math>x_0</math> имеет место неравенство
    <math>|f(x)| \leqslant C |g(x)|</math>;
  • <math>f</math> является «о» малым от <math>g</math> при <math>x\to x_0</math>, если для любого <math>\varepsilon>0</math> найдется такая проколотая окрестность <math>U_{x_0}'</math> точки <math>x_0</math>, что для всех <math>x\in U_{x_0}'</math> имеет место неравенство
    <math>|f(x)| < \varepsilon |g(x)|.</math>

Иначе говоря, в первом случае отношение <math>\frac{|f|}{|g|} \le C</math> в окрестности точки <math>x_0</math> (т.е ограничено сверху), а во втором оно стремится к нулю при <math>x\to x_0</math>.

Обозначение

Обычно выражение «<math>f</math> является <math>O</math> большим (<math>o</math> малым) от <math>g</math>» записывается с помощью равенства <math>f(x) = O(g(x))</math> (соответственно, <math>f(x) = o(g(x))</math> ).

Это обозначение очень удобно, но требует некоторой осторожности при использовании (а потому в наиболее элементарных учебниках его могут избегать). Дело в том, что это не равенство в обычном смысле, а несимметричное отношение.

В частности, можно писать

<math> f(x) = O(g(x)) </math> (или <math> f(x) = o(g(x)) </math> ),

но выражения

<math> O(g(x)) = f(x) </math> (или <math> o(g(x)) = f(x) </math>)

бессмысленны.

Другой пример: при <math> x \rightarrow 0 </math> верно, что

<math> O(x^2) = o(x) </math>

но неверно, что

<math> o(x) = O(x^2) </math>.

При любом x верно

<math> o(x) = O(x) </math>,

т.е. бесконечно малая величина является ограниченной, но неверно, что ограниченная величина является бесконечно малой:

<math> O(x) = o(x) </math>.

Вместо знака равенства методологически правильнее было бы употреблять знаки принадлежности и включения, понимая <math>O({\,})</math> и <math>o({\,})</math> как обозначения для множеств функций, то есть, используя запись в форме

<math> x^3 + x^2 \in O(x^3) </math>

или

<math>\mathop O(x^2)\subset o(x)</math>

вместо, соответственно,

<math> x^3 + x^2 = O(x^3) </math>

и

<math>\mathop O(x^2) = o(x)</math>

Однако на практике такая запись встречается крайне редко, в основном, в простейших случаях.

При использовании данных обозначений должно быть явно оговорено (или очевидно из контекста), о каких окрестностях (одно- или двусторонних; содержащих целые, вещественные или комплексные числа и т. п.) и о каких допустимых множествах функций идет речь (поскольку такие же обозначения употребляются и применительно к функциям многих переменных, к функциям комплексной переменной, к матрицам и др.).

Другие подобные обозначения

Для функций <math>f(n)</math> и <math>g(n)</math> при <math>n \to n_0</math> используются следующие обозначения:

Обозначение Интуитивное объяснение Определение
<math>f(n) \in O(g(n))</math> <math>f</math> ограничена сверху функцией <math>g</math> (с точностью до постоянного множителя) асимптотически f(n)| \leq C|g(n)| </math>
<math>f(n) \in \Omega(g(n))</math> <math>f</math> ограничена снизу функцией <math>g</math> (с точностью до постоянного множителя) асимптотически g(n)| \leq |f(n)|</math>
<math>f(n) \in \Theta(g(n))</math> <math>f</math> ограничена снизу и сверху функцией <math>g</math> асимптотически g(n)| \leq |f(n)| \leq C'|g(n)| </math>
<math>f(n) \in o(g(n))</math> <math>g</math> доминирует над <math>f</math> асимптотически f(n)| < C|g(n)|</math>
<math>f(n) \in \omega(g(n))</math> <math>f</math> доминирует над <math>g</math> асимптотически g(n)| < |f(n)|</math>
<math>f(n) ~\sim~ g(n)</math> <math>f</math> эквивалентна <math>g</math> асимптотически <math>\lim_{n \to n_0} \frac{f(n)}{g(n)} = 1</math>

где <math>U</math> — проколотая окрестность точки <math>n_0</math>.

Основные свойства

Транзитивность

  • <math>\begin{matrix}f(n)=\Theta(g(n)) \land g(n)=\Theta(h(n)) & \Rightarrow & f(n) = \Theta (h(n)) \\

f(n)=O(g(n)) \land g(n)=O (h(n)) & \Rightarrow & f(n) = O (h(n)) \\ f(n)=\Omega(g(n)) \land g(n)=\Omega(h(n)) & \Rightarrow & f(n) = \Omega(h(n)) \\ f(n)=o(g(n)) \land g(n)= o (h(n)) & \Rightarrow & f(n) = o (h(n)) \\ f(n)=\omega(g(n)) \land g(n)=\omega(h(n)) & \Rightarrow & f(n) = \omega(h(n))\end{matrix}</math>

Рефлексивность

  • <math>f(n)=\Theta(f(n))</math>
  • <math>f(n)=O(f(n))</math>
  • <math>f(n)=\Omega(f(n))</math>

Симметричность

  • <math> f(n)=\Theta(g(n)) \Leftrightarrow g(n)=\Theta(f(n)) </math>

Перестановочная симметрия

<math> \begin{matrix} f(n)= O(g(n)) & \Leftrightarrow & g(n)=\Omega(f(n)) \\ f(n)= o(g(n)) & \Leftrightarrow & g(n)=\omega(f(n)) \end{matrix}</math>

Другие

  • <math> C \cdot o(f) = o(f) </math>
<math> C \cdot O(f) = O(f) </math>
  • <math> o(C \cdot f) = o(f) </math>
<math> O(C \cdot f) = O(f) </math>
и, как следствия,
<math> o(-f) = o(f) </math>
<math> O(-f) = O(f) </math>
  • <math> o(f) + o(f) = o(f) </math>
<math> o(f) + O(f) = O(f) + O(f) = O(f) </math>
  • <math> O(f) \cdot O(g) = O(fg) </math>
<math> o(f) \cdot O(g) = o(f) \cdot o(g) = o(fg) </math>
  • <math> O(O(f)) = O(f) </math>
<math> o(o(f)) = o(O(f)) = O(o(f)) = o(f) </math>

Асимптотические обозначения в уравнениях

  • Если в правой части уравнения находится только асимптотическое обозначение (например <math>n = O(n^2)</math>), то знак равенства обозначает принадлежность множеству (<math>n \in O(n^2)</math>).
  • Если в уравнении асимптотические обозначения встречается в другой ситуации, они рассматриваются как подставляемые взамен их некоторые функции. Например, при x → 0 формула <math>e^x-1 = x + o(x)</math> обозначает, что <math>e^x-1 = x + f(x)</math>, где <math>f(x)</math> — функция, о которой известно только то, что она принадлежит множеству <math>o(x)</math>. Предполагается, что таких функций в выражении столько, сколько раз встречаются в нём асимптотические обозначения. Например,   <math>\sum_{i=0}^nO(n_i^2)</math>   — содержит только одну функцию из класса <math>O(n^2)</math>.
  • Если асимптотические обозначения встречаются в левой части уравнения, используют следующее правило:
    какие бы мы функции ни выбрали (в соответствии с предыдущим правилом) взамен асимптотических обозначений в левой части уравнения, можно выбрать функции вместо асимптотических обозначений (в соответствии с предыдущим правилом) в правой части так, что уравнение будет правильным.
    Например, запись <math>x+o(x)=O(x)</math> обозначает, что для любой функции <math>f(x)\in o(x)</math>, существует некоторая функция <math>g(x)\in O(x)</math> такая, что выражение <math>x+f(x)=g(x)</math> — верно для всех <math>x</math>.
  • Несколько таких уравнений могут быть объединены в цепочки. Каждое из уравнений в таком случае следует интерпретировать в соответствии с предыдущим правилом.
    Например: <math>4n^4+4n^2+1=4n^4+\Theta(n^2)=\Theta(n^4)</math>. Отметим, что такая интерпретация подразумевает выполнение соотношения <math>4n^4+4n^2+1=\Theta(n^4)</math>.

Приведенная интерпретация подразумевает выполнение соотношения:

<math>\left. \begin{matrix}A = B \\ B = C \end{matrix} \right\} \Rightarrow A = C</math>, где A, B, C — выражения, которые могут содержать асимптотические обозначения.

Примеры использования

  • <math>e^x = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + ... + \frac{x^n}{n!} + ... = 1 + x + \frac{x^2}{2} + O(x^3)</math> при <math>x \rightarrow 0</math>
  • <math>n! = O\left(\left(\frac{n}{e}\right)^{n + \frac{1}{2}}\right)</math> при <math>n \rightarrow \infty</math> (следует из формулы Стирлинга)
  • <math>T(n)=(n+1)^2=O(n^2)</math> при <math>n \rightarrow \infty</math>.
При <math>n \geq 1</math> выполнено неравенство <math>(n+1)^2<4n^2</math>. Поэтому положим <math>n_0=1, c=4</math>.
Отметим, что нельзя положить <math>n_0=0</math>, так как <math>T(0)=1</math> и, следовательно, это значение при любой константе <math>c</math> больше <math>c \cdot 0^2=0</math>.
  • Функция <math>T(n)=3n^3+2n^2</math> при <math>n \rightarrow \infty</math> имеет степень роста <math>O(n^3)</math>.
Чтобы это показать, надо положить <math>n_0=0</math> и <math>c=5</math>. Можно, конечно, сказать, что <math>T(n)</math> имеет порядок <math>O(n^4)</math>, но это более слабое утверждение, чем то, что <math>T(n) = O(n^3)</math>.
  • Докажем, что функция <math>3^n</math> при <math>n \rightarrow \infty</math> не может иметь порядок <math>O(2^n)</math>.
Предположим, что существуют константы <math>c</math> и <math>n_0</math> такие, что для всех <math>n \geq n_0</math> выполняется неравенство <math>3^n \leq c \cdot 2^n</math>.
Тогда <math>c \geq \left( \frac{3}{2} \right)^n</math> для всех <math> n \geq n_0 </math>. Но <math> \left( \frac{3}{2} \right)^n </math> принимает любое, как угодно большое, значение при достаточно большом <math>n</math>, поэтому не существует такой константы <math>c</math>, которая могла бы мажорировать <math> \left( \frac{3}{2} \right)^n</math> для всех <math>n</math> больших некоторого <math>n_0</math>.
  • <math>T(n)=n^3+2n^2 = \Omega(n^3), n \rightarrow \infty </math>.
Для проверки достаточно положить <math>c=1</math>. Тогда <math> T(n) \geq cn^3 </math> для <math>n=0, 1, ...</math>.

История

Обозначение «„O“ большое» введено немецким математиком Паулем Бахманом во втором томе его книги «Analytische Zahlentheorie» (Аналитическая теория чисел), вышедшем в 1894 году. Обозначение «„о“ малое» впервые использовано другим немецким математиком, Эдмундом Ландау в 1909 году; с работами последнего связана и популяризация обоих обозначений, в связи с чем их также называют символами Ландау. Обозначение пошло от немецкого слова «Ordnung» (порядок)[2].

См. также

Напишите отзыв о статье "«O» большое и «o» малое"

Примечания

  1. И. А. Шведов. Компактный курс математического анализа. Часть 1. Функции одной переменной. Новосибирск, 2003. С.43.
  2. D.E. Knuth [www.phil.uu.nl/datastructuren/09-10/knuth_big_omicron.pdf Big Omicron and big Omega and big Theta] (англ.) : Article. — ACM Sigact News, 1976. — Т. 8, № 2. — С. 18-24.

Литература

  • Д. Грин, Д. Кнут. Математические методы анализа алгоритмов. — Пер. с англ. — М.: Мир, 1987. — 120 с.
  • Дж. Макконелл. Основы современных алгоритмов. — Изд. 2 доп. — М.: Техносфера, 2004. — 368 с. — ISBN 5-94836-005-9.
  • Джон Э. Сэвидж. Сложность вычислений. — М.: Факториал, 1998. — 368 с. — ISBN 5-88688-039-9.
  • В. Н. Крупский. Введение в сложность вычислений. — М.: Факториал Пресс, 2006. — 128 с. — ISBN 5-88688-083-6.
  • Herbert S. Wilf. [www.math.upenn.edu/~wilf/AlgComp3.html Algorithms and Complexity].
  • Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 3. Рост функций // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — С. 87—108. — ISBN 5-8459-0857-4.
  • Бугров, Никольский. Высшая математика, том 2.
  • Dionysis Zindros. [habrahabr.ru/post/196560/ Введение в анализ сложности алгоритмов] (рус.) (2012). Проверено 11 октября 2013.

Отрывок, характеризующий «O» большое и «o» малое

Французская армия в той же пропорции таяла и уничтожалась от Москвы до Вязьмы, от Вязьмы до Смоленска, от Смоленска до Березины, от Березины до Вильны, независимо от большей или меньшей степени холода, преследования, заграждения пути и всех других условий, взятых отдельно. После Вязьмы войска французские вместо трех колонн сбились в одну кучу и так шли до конца. Бертье писал своему государю (известно, как отдаленно от истины позволяют себе начальники описывать положение армии). Он писал:
«Je crois devoir faire connaitre a Votre Majeste l'etat de ses troupes dans les differents corps d'annee que j'ai ete a meme d'observer depuis deux ou trois jours dans differents passages. Elles sont presque debandees. Le nombre des soldats qui suivent les drapeaux est en proportion du quart au plus dans presque tous les regiments, les autres marchent isolement dans differentes directions et pour leur compte, dans l'esperance de trouver des subsistances et pour se debarrasser de la discipline. En general ils regardent Smolensk comme le point ou ils doivent se refaire. Ces derniers jours on a remarque que beaucoup de soldats jettent leurs cartouches et leurs armes. Dans cet etat de choses, l'interet du service de Votre Majeste exige, quelles que soient ses vues ulterieures qu'on rallie l'armee a Smolensk en commencant a la debarrasser des non combattans, tels que hommes demontes et des bagages inutiles et du materiel de l'artillerie qui n'est plus en proportion avec les forces actuelles. En outre les jours de repos, des subsistances sont necessaires aux soldats qui sont extenues par la faim et la fatigue; beaucoup sont morts ces derniers jours sur la route et dans les bivacs. Cet etat de choses va toujours en augmentant et donne lieu de craindre que si l'on n'y prete un prompt remede, on ne soit plus maitre des troupes dans un combat. Le 9 November, a 30 verstes de Smolensk».
[Долгом поставляю донести вашему величеству о состоянии корпусов, осмотренных мною на марше в последние три дня. Они почти в совершенном разброде. Только четвертая часть солдат остается при знаменах, прочие идут сами по себе разными направлениями, стараясь сыскать пропитание и избавиться от службы. Все думают только о Смоленске, где надеются отдохнуть. В последние дни много солдат побросали патроны и ружья. Какие бы ни были ваши дальнейшие намерения, но польза службы вашего величества требует собрать корпуса в Смоленске и отделить от них спешенных кавалеристов, безоружных, лишние обозы и часть артиллерии, ибо она теперь не в соразмерности с числом войск. Необходимо продовольствие и несколько дней покоя; солдаты изнурены голодом и усталостью; в последние дни многие умерли на дороге и на биваках. Такое бедственное положение беспрестанно усиливается и заставляет опасаться, что, если не будут приняты быстрые меры для предотвращения зла, мы скоро не будем иметь войска в своей власти в случае сражения. 9 ноября, в 30 верстах от Смоленка.]
Ввалившись в Смоленск, представлявшийся им обетованной землей, французы убивали друг друга за провиант, ограбили свои же магазины и, когда все было разграблено, побежали дальше.
Все шли, сами не зная, куда и зачем они идут. Еще менее других знал это гений Наполеона, так как никто ему не приказывал. Но все таки он и его окружающие соблюдали свои давнишние привычки: писались приказы, письма, рапорты, ordre du jour [распорядок дня]; называли друг друга:
«Sire, Mon Cousin, Prince d'Ekmuhl, roi de Naples» [Ваше величество, брат мой, принц Экмюльский, король Неаполитанский.] и т.д. Но приказы и рапорты были только на бумаге, ничто по ним не исполнялось, потому что не могло исполняться, и, несмотря на именование друг друга величествами, высочествами и двоюродными братьями, все они чувствовали, что они жалкие и гадкие люди, наделавшие много зла, за которое теперь приходилось расплачиваться. И, несмотря на то, что они притворялись, будто заботятся об армии, они думали только каждый о себе и о том, как бы поскорее уйти и спастись.


Действия русского и французского войск во время обратной кампании от Москвы и до Немана подобны игре в жмурки, когда двум играющим завязывают глаза и один изредка звонит колокольчиком, чтобы уведомить о себе ловящего. Сначала тот, кого ловят, звонит, не боясь неприятеля, но когда ему приходится плохо, он, стараясь неслышно идти, убегает от своего врага и часто, думая убежать, идет прямо к нему в руки.
Сначала наполеоновские войска еще давали о себе знать – это было в первый период движения по Калужской дороге, но потом, выбравшись на Смоленскую дорогу, они побежали, прижимая рукой язычок колокольчика, и часто, думая, что они уходят, набегали прямо на русских.
При быстроте бега французов и за ними русских и вследствие того изнурения лошадей, главное средство приблизительного узнавания положения, в котором находится неприятель, – разъезды кавалерии, – не существовало. Кроме того, вследствие частых и быстрых перемен положений обеих армий, сведения, какие и были, не могли поспевать вовремя. Если второго числа приходило известие о том, что армия неприятеля была там то первого числа, то третьего числа, когда можно было предпринять что нибудь, уже армия эта сделала два перехода и находилась совсем в другом положении.
Одна армия бежала, другая догоняла. От Смоленска французам предстояло много различных дорог; и, казалось бы, тут, простояв четыре дня, французы могли бы узнать, где неприятель, сообразить что нибудь выгодное и предпринять что нибудь новое. Но после четырехдневной остановки толпы их опять побежали не вправо, не влево, но, без всяких маневров и соображений, по старой, худшей дороге, на Красное и Оршу – по пробитому следу.
Ожидая врага сзади, а не спереди, французы бежали, растянувшись и разделившись друг от друга на двадцать четыре часа расстояния. Впереди всех бежал император, потом короли, потом герцоги. Русская армия, думая, что Наполеон возьмет вправо за Днепр, что было одно разумно, подалась тоже вправо и вышла на большую дорогу к Красному. И тут, как в игре в жмурки, французы наткнулись на наш авангард. Неожиданно увидав врага, французы смешались, приостановились от неожиданности испуга, но потом опять побежали, бросая своих сзади следовавших товарищей. Тут, как сквозь строй русских войск, проходили три дня, одна за одной, отдельные части французов, сначала вице короля, потом Даву, потом Нея. Все они побросали друг друга, побросали все свои тяжести, артиллерию, половину народа и убегали, только по ночам справа полукругами обходя русских.
Ней, шедший последним (потому что, несмотря на несчастное их положение или именно вследствие его, им хотелось побить тот пол, который ушиб их, он занялся нзрыванием никому не мешавших стен Смоленска), – шедший последним, Ней, с своим десятитысячным корпусом, прибежал в Оршу к Наполеону только с тысячью человеками, побросав и всех людей, и все пушки и ночью, украдучись, пробравшись лесом через Днепр.
От Орши побежали дальше по дороге к Вильно, точно так же играя в жмурки с преследующей армией. На Березине опять замешались, многие потонули, многие сдались, но те, которые перебрались через реку, побежали дальше. Главный начальник их надел шубу и, сев в сани, поскакал один, оставив своих товарищей. Кто мог – уехал тоже, кто не мог – сдался или умер.


Казалось бы, в этой то кампании бегства французов, когда они делали все то, что только можно было, чтобы погубить себя; когда ни в одном движении этой толпы, начиная от поворота на Калужскую дорогу и до бегства начальника от армии, не было ни малейшего смысла, – казалось бы, в этот период кампании невозможно уже историкам, приписывающим действия масс воле одного человека, описывать это отступление в их смысле. Но нет. Горы книг написаны историками об этой кампании, и везде описаны распоряжения Наполеона и глубокомысленные его планы – маневры, руководившие войском, и гениальные распоряжения его маршалов.
Отступление от Малоярославца тогда, когда ему дают дорогу в обильный край и когда ему открыта та параллельная дорога, по которой потом преследовал его Кутузов, ненужное отступление по разоренной дороге объясняется нам по разным глубокомысленным соображениям. По таким же глубокомысленным соображениям описывается его отступление от Смоленска на Оршу. Потом описывается его геройство при Красном, где он будто бы готовится принять сражение и сам командовать, и ходит с березовой палкой и говорит:
– J'ai assez fait l'Empereur, il est temps de faire le general, [Довольно уже я представлял императора, теперь время быть генералом.] – и, несмотря на то, тотчас же после этого бежит дальше, оставляя на произвол судьбы разрозненные части армии, находящиеся сзади.
Потом описывают нам величие души маршалов, в особенности Нея, величие души, состоящее в том, что он ночью пробрался лесом в обход через Днепр и без знамен и артиллерии и без девяти десятых войска прибежал в Оршу.
И, наконец, последний отъезд великого императора от геройской армии представляется нам историками как что то великое и гениальное. Даже этот последний поступок бегства, на языке человеческом называемый последней степенью подлости, которой учится стыдиться каждый ребенок, и этот поступок на языке историков получает оправдание.
Тогда, когда уже невозможно дальше растянуть столь эластичные нити исторических рассуждений, когда действие уже явно противно тому, что все человечество называет добром и даже справедливостью, является у историков спасительное понятие о величии. Величие как будто исключает возможность меры хорошего и дурного. Для великого – нет дурного. Нет ужаса, который бы мог быть поставлен в вину тому, кто велик.
– «C'est grand!» [Это величественно!] – говорят историки, и тогда уже нет ни хорошего, ни дурного, а есть «grand» и «не grand». Grand – хорошо, не grand – дурно. Grand есть свойство, по их понятиям, каких то особенных животных, называемых ими героями. И Наполеон, убираясь в теплой шубе домой от гибнущих не только товарищей, но (по его мнению) людей, им приведенных сюда, чувствует que c'est grand, и душа его покойна.