9.2 СИМВОЛ «О»

В 1894 г. Пауль Бахман придумал замечательное обозначение для асимптотического анализа. В последующие годы его популярности способствовали Эдмунд Ландау и др. Мы встречаем это обозначение в формулах наподобие

которая говорит нам, что гармоническое число равно натуральному логарифму плюс константа Эйлера плюс некоторая величина, которая составляет большое от 1 на Эта последняя величина точно не определена, однако, какой бы она ни была, обозначение позволяет утверждать, что она не превосходит константу, умноженную на

Красота символа в том, что он скрывает несущественные детали и позволяет сконцентрироваться на главных особенностях поведения: величину можно считать пренебрежимо малой, если только нас не интересуют величины, отличающиеся от лишь постоянным множителем.

Более того, символ удобно использовать внутри формул. Если мы захотим выразить соотношение (9.10) с использованием обозначений, введенных в разд. 9.1, то нам придется перенести в левую часть и сформулировать результат в более слабой форме, например,

или же в сильной форме:

Символ позволяет нам указывать нужное количество деталей на месте, без перестановки членов.

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

Н.Г. де Брейн начал свою книгу Асимптотические методы в анализе [97] с рассмотрения обозначения „Эль большое", которое помогает понять смысл „О большого". Если мы запишем для обозначения числа, чья абсолютная величина меньше 5 (не говоря, однако, что это за число), то мы сможем выполнять кое-какие вычисления, даже не зная всей правды. Так, можно вывести некоторые формулы, например, и т.д. Однако отсюда нельзя заключить, что поскольку левая часть может, например, равняться . Фактически, лучшее, что можно утверждать, это

Обозначение «О большое» Бахмана аналогично обозначению «L большое», но оно еще менее определенно: обозначает число, абсолютная величина которого не превосходит константу, умноженную на Мы не говорим, что это за число и даже не говорим, что это за константа. Разумеется, понятие «константы» бессмысленно, если нет чего-либо меняющегося; поэтому мы используем символ только в тех случаях, когда имеется хотя бы одна величина (скажем, ), значение которой меняется. Тогда формула

означает, что существует такая константа С, что

а если обозначение использовано внутри формулы, то оно означает функцию удовлетворяющую (9.12). Значения функции неизвестны, однако мы все же знаем, что они не слишком велики. Аналогично, введенная ранее функция

представляет собой неопределенную функцию значения которой удовлетворяют неравенству Главное различие между L и О в том, что символ включает неопределенную константу С; каждое вхождение О может подразумевать различные С, но каждая из этих констант не зависит от

Так, например, мы знаем, что сумма первых квадратов равна

Мы можем записать

поскольку для всех целых Аналогично, можно получить более точную формулу

можно также небрежно отбросить часть информации и записать

Определение О отнюдь не заставляет нас давать наилучшую оценку.

Но минуточку. Что, если переменная — не целочисленная? Как быть с формулой вроде где х — вещественное число? Здесь уже нельзя сказать, что поскольку отношение неограниченно растет при Нельзя также сказать, что поскольку отношение неограниченно растет, когда х стремится к Так что мы, судя по всему, вовсе не можем использовать символ для оценки

Эта дилемма разрешается благодаря тому, что на переменные, используемые с О, обычно накладываются какие-либо ограничения. Если, например, мы поставим условие, что или что где — произвольная положительная константа, или что х — целое число, то мы сможем записать Если же наложено условие или с, где с — произвольная положительная константа, то в этом случае S(x) = О(х). «О большое» зависит от контекста, от ограничений на используемые переменные.

Эти ограничения часто задаются в виде предельных соотношений. Например, мы могли бы сказать, что

Такая запись означает, что условия, накладываемые обозначением О, предполагаются выполненными, когда „близко" к ; нас не волнует, что происходит при не слишком больших Более

того, мы даже не определяем точно, что означает «близко»; в такой ситуации каждое вхождение О подразумевает существование двух констант С и по, таких, что

Значения С и по могут быть разными для разных О, но они не зависят от Аналогично, запись

означает, что существуют две константы , такие, что

Предельное значение не обязательно равно или 0; справедлива запись

поскольку, как можно доказать, если

Мы постепенно, на протяжении нескольких страниц, развили наше определение О, начав со вполне очевидных вещей, и получили в итоге нечто, представляющееся ужасно сложным; теперь у нас О представляет неопределенную функцию и одну или две неопределенные константы, зависящие от контекста. Все это может показаться слишком сложным для сколько-нибудь разумного обозначения, но это еще не все! Еще одна тонкость пока ускользнула от нашего внимания. А именно, следует осознавать, что запись

вполне корректна, но в этом равенстве ни в коем случае нельзя менять местами правую и левую части. В противном случае мы можем прийти к нелепым выводам, наподобие исходя из верных тождеств Работая с символом и другими формулами, включающими не полностью определенные величины, мы имеем дело с односторонними равенствами. Правая часть уравнения содержит не больше информации, чем левая, и фактически может содержать меньше информации; правая часть является „огрублением" левой.

Если говорить строго формально, то запись обозначает не какую-то одну функцию , а сразу все множество функций таких, что для некоторой константы С. Обычная формула не включающая символа О, обозначает множество, содержащее одну функцию Если суть множества функций от то запись обозначает множество всех функций вида где другие обозначения вроде определяются аналогично. Тогда «равенство» между двумя

такими множествами функций есть, строго говоря, теоретикомножественное включение; знак действительности означает Эти формальные определения подводят под все наши манипуляции с О твердую логическую основу.

Так, "уравнение"

означает, что где есть множество всех функций вида для которых найдется константа такая, что есть множество всех функций для которых найдется константа такая, что Мы можем строго доказать это «равенство», если возьмем произвольный элемент из левой части и покажем, что он принадлежит правой части: пусть таково, что нам следует доказать, что существует такая константа что Константа решает проблему, поскольку для всех целых

Но если в действительности означает то почему бы нам не писать явно вместо превратного использования знака равенства? Тому есть четыре причины.

Во-первых, традиция. Начали использовать символ О со знаком равенства теоретико-числовики, и эта практика получила распространение. Мы давно убедились, что пытаться изменить привычки математического сообщества — дело безнадежное.

Во-вторых, традиция. Программисты вполне привыкли видеть знак равенства не на месте — многие годы в программах на Фортране и Бейсике мы писали присваивания вида Одной неправильной трактовкой больше, одной меньше — какая разница!

В-третьих, традиция. Мы часто произносим знак словом «есть». Например, формулу можно произнести как „Аш энное есть О большое от лог эн". Но слово ‘есть’ несимметрично. Мы говорим, что птицы есть животные, но не можем сказать, что животные есть птицы; „животное" — это огрубление понятия „птица"

И, в-четвертых, для наших целей такое обозначение весьма естественно. Если мы ограничимся лишь ситуациями, где символ О целиком занимает правую часть формулы — как в аппроксимации гармонических чисел, или в оценке времени работы алгоритма сортировки, неважно, какой знак используется, или какой-либо еще. Однако если символ О использовать внутри выражений, как мы часто делаем в асимптотическом анализе, то нашей интуиции отвечает трактовка знака как равенства, а величины вроде как чего-то очень маленького.

Поэтому мы и дальше будем использовать и будем считать не полностью определенной функцией, имея в

виду, что в случае необходимости мы всегда сможем вернуться к теоретико-множественным определениям.

Всесторонне рассматривая определение, мы обязаны отметить еще одну техническую деталь. Если в формуле используется несколько переменных, то символ О представляет множество функций от двух или более переменных, а не только от одной. В область определения каждой функции входят все переменные, которые в данном контексте „свободны" для изменения.

Тут есть некоторая тонкость ввиду того, что переменные могут иметь смысл лишь в части выражения, если они связаны знаком или подобным. Посмотрим внимательно, например, на соотношение

Выражение в левой части отвечает множеству всех функций от двух переменных вида для которых найдется константа С, такая, что для 0 к Сумма таких множеств функций для есть множество всех функций вида

где удовлетворяет сформулированному условию. Поскольку

то все такие функции принадлежат правой части следовательно, (9.16) справедливо.

Иногда О-обозначения понимают неправильно, считая, что дает точный порядок роста; символ О используется так, как будто он определяет наряду с верхней границей также нижнюю. Так, можно услышать, что некий алгоритм сортировки чисел неэффективен, „поскольку его время работы составляет Однако время работы вовсе не означает, что это время не есть также Для указания нижней границы имеется другое обозначение — «большая Омега»:

Мы имеем тогда и только тогда, когда При достаточно больших алгоритм сортировки с временем работы неэффективен в сравнении с алгоритмом, время работы которого есть

И, наконец, символ «большая Тета» указывает точный порядок роста:

Мы будем иметь тогда и только тогда, когда в обозначениях, введенных ранее, в (9.8).

Эдмунд Ландау [180] изобрел символ «о малое»,

Это есть, по-существу, отношение из (9.3). Имеем также

Многие авторы используют в асимптотических формулах однако почти всегда предпочтительнее более явное выражение с Например, среднее время работы алгоритма, называемого «сортировка методом пузырька», зависит от асимптотического значения суммы Элементарные методы асимптотического анализа позволяют доказать тот факт, что это означает, что отношение стремится к 1 при Однако для того, чтобы лучше понять поведение следует рассмотреть не отношение, а разность

Значения в среднем столбце не очень убедительны; это едва ли может считаться аргументом в пользу быстрой сходимости к 1, да и есть ли вообще сходимость? Однако правый столбец показывает, что значение действительно весьма близко к . Таким образом, мы гораздо лучше охарактеризуем поведение если сможем вывести формулы наподобие

или даже более точную оценку вида

Для доказательства результатов с О требуются более сильные методы асимптотического анализа, однако дополнительные усилия, потраченные на изучение этих методов, многократно окупаются лучшим пониманием асимптотики, которое дают О-оценки.

Более того, время работы многих алгоритмов сортировки имеет вид

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

Прежде чем продолжить изучение О большого, поговорим немного об одном маленьком элементе математического стиля. В этой главе используется три различных обозначения логарифма: В связи с компьютерными методами мы часто используем поскольку в таких случаях двоичный логарифм оказывается наиболее подходящим; в чистой математике часто используется поскольку формулы с натуральным логарифмом просты и изящны. Но что такое Неужели это „обычный десятичный логарифм, изучаемый в старших классах — „обычный" логарифм, который оказывается очень необычным как для математики, так и для информатики? Да, это так; вместе с тем, многие математики вносят путаницу в этот вопрос, используя для натурального или двоичного логарифма. Здесь нет единого соглашения, однако можно вздохнуть с облегчением, если логарифм встречается внутри О-обозначения, поскольку для О несущественны мультипликативные константы. При между нет никакой разницы; аналогично, нет разницы между Мы можем выбрать, что нам больше нравится; вариант представляется привлекательным, поскольку его удобнее произносить. Поэтому мы, как правило, будем использовать во всех тех случаях, когда это способствует благозвучию, не приводя к двусмысленности.