Асимптотические оценки (формализм)

Для характеристики роста сложности по числу сравнений сортиров­ки простыми вставками первого и второго типа мы можем исполь­зовать известный из математического анализа символ O и написать T{n) = O{n²) (здесь и далее n-> оо). Мы можем также выделить глав­ные по росту слагаемые в (1.3):

T{n) = n² + O{n), T ₂ (n) = |n² + O(n), (2.1)

хотя в этом и нет ощутимого практического смысла в силу простоты функций T](n), T]2(n). В то же время, как это хорошо известно, асимп­тотическая формула f{n) = O{g{n)) является удобным средством оце­нивания нетривиально устроенной функции f(n) с помощью более простой функции g(n); столь же полезными оказываются и оценки вида f(n) = o(g(n)). Но когда мы говорим, что сортировка выбором, пузырьковая сортировка и сортировка простыми вставками имеют квадратичные сложности, мы имеем в виду не только то, что соответ­ствующие сложности допускают оценку O{n²), но что эти сложности являются величинами порядка n²; в математическом анализе это ино­гда записывается как T{n)~n², где T{n)— рассматриваемая функция, в данном случае — сложность. В последние годы в теории сложности алгоритмов вместо f{n)~g{n) стали писать f(n) = 6(g(n)).

Определение 2.1.Функции f(n) и g{n) имеют одинаковый порядок (пишут f(n) = 6(g(n))) тогда и только тогда, когда найдутся положи­тельные c_ъ c₂, N такие, что неравенства

cilg(n)|sS|f(n)|sSc₂|g(n)| (2.2)

выполнены для всех n>N.

Без труда проверяется, что отношение «иметь одинаковый поря­док» является отношением эквивалентности на множестве функций,

§ 2. Асимптотические оценки (формализм)

определенных для всех достаточно больших значений п (в нашем слу­чае эти значения целые). Несимметричность записи /(n) = 6(g(n)) в сравнении с записью /(n) xg(n) (/(п) и g{n) как бы не равноправ­ны в первой записи, хотя имеем дело с отношением эквивалентно­сти) объясняется тем, что обычно эту запись используют, когда g{n) проще, чем /(п).

Итак, для сложности Т{п) по числу сравнений для любого из упо­мянутых алгоритмов сортировки мы имеем Г(п) = 6(п²). Это более сильное утверждение, чем Т{п) = 0{п²), так как Т{п) = 0{п²) является лишь асимптотической верхней оценкой: в соответствии с известным из математического анализа определением

f{n) = 0{g{n)) <^> 3_C;N>0 V_n>N |/(n)|sSc|g(n)|,

например, n = 0{п²), но неверно, что п = в(п²). Здесь и далее, пользу­ясь кванторами 3, V, мы записываем связываемые ими переменные, равно как и условия, определяющие множества значений этих пе­ременных, в виде индексных выражений при кванторах. Это часто позволяет обходиться без дополнительных скобок и облегчает чтение формул.

Иногда бывают полезными нижние асимптотические оценки.

Определение 2.2.Соотношение /(n) = fi(g(n)) имеет место тогда и только тогда, когда найдутся положительные с, JV такие, что для всех n>N выполнено |/(n)|^c|g(n)|.

Следующее предложение выводится из определений символов О, П и в.

Предложение 2.1.Соотношение /(n) = 6(g(n)) имеет место тогда и только тогда, когда одновременно /(п) = 0(g(n)) и /(n) = fi(g(n)); помимо этого, /(п) = ОДп)) тогда и только тогда, когда g{n) = = 0(/(п)).

Если размер входа является целым положительным числом, то воз­никающие функции являются последовательностями. Для единообра­зия мы, как правило, будем говорить о функциях, подразумевая, но не упоминая специально, что каждая такая функция определена лишь для целых положительных значений аргумента (возможно даже, толь­ко для достаточно больших целых положительных значений аргумен­та). Итак, при п->оо оценки вида /(n) = A(g(n)), где Л —один из символов Г2, О, в, предполагают, что функции f{n),g{n) определе­ны для всех достаточно больших п. Соответствующее неравенство из

20 Глава 1. Сложности алгоритмов как функции числовых аргументов

числа

\f{n)\^c₁\g{n)\, |f(n)|sSc₂|g(n)|, cilgCnOlsSlfCnOlsScalgCnOI (2.3)

тоже, в соответствии с определением, должно выполняться лишь для n, больших некоторого N. Заметим, однако, что если f(n) и g{n) определены для всех nsN⁺ и принимают при 1 ^ n ^ N ненулевые значения, то можно считать, что соответствующее неравенство из пе­речисленных в (2.3) выполняется для всех n, так как, положив

• 1f(n)1 1f(n)1

m= mm т-7-77, M= max т-т-тт,

IsCnsCN \g(n)\ IsCnsCN \g(n)\

мы можем заменить c_ъc₂ в (2.3) на c[ = тт{c_ъm}, c'₂ = тт{c₂,M}. Это замечание в некоторых случаях будет для нас полезным.

Вернемся к примеру 1.2. Для сложности алгоритма пробных деле­ний было бы ошибкой утверждать, что его сложность по числу деле­ний есть 6(лn)- Но оценка O(лn), разумеется, верна и, более того, является точной в смысле следующего определения.

Определение 2.3.Если имеет место оценка f(n) = O(g(n)), то она называется точной, коль скоро существует неограниченно возраста­ющая последовательность неотрицательных целых чисел {n_k} такая, что для ₄>{k) = f{n_k), Vk) = g(n_k) имеет место у(k) = Qty (k)).

Для упомянутых ip(k) и t/>(k) в силу этого определения и семан­тики символа в выполнено y>(k) = 6(i/>(k)).

При рассмотрении алгоритма пробных делений для доказатель­ства точности оценки O(лn) можно взять n_k равным k-му простому числу, k = 1,2,...

Понятие точности оценки вида f(n) = O(,g(n)) можно определить также с помощью знакомого из математического анализа символа o; напомним, что u(,n) = o(v(_n)) при n—><*>, коль скоро u{n) = a{n)v{n) и lima(n) = 0.

Предложение 2.2.Пусть f{n) = O{g{n)). Эта оценка является точной, если и только если неверно, что f(n) = o(g(n)).

Доказательство. Пусть оценка является точной, и {nj —воз­растающая последовательность, о которой говорится в определе­нии 2.3. Тогда существует положительная константа c такая, что \f{n_k)\^c\g{n_k)\, k = l,2, ..., и соотношение f{n) = o{g{n)) места не имеет. Обратно, если неверно, что f(n) = o(g(n)), то по определению символа o существуют е > 0 и возрастающая последовательность {n_k} натуральных чисел такие, что |f(n_k) | ^ e|g(n_k) |, k = 1, 2, ... Если при

§ 2. Асимптотические оценки (формализм)

этом выполнена оценка /(n) = 0(g(n)), то эта оценка точна в соот­
ветствии с определением 2.3. □

Для рассматриваемой сложности алгоритма пробных делений не верна, скажем, оценка O(logn), потому что для этой сложности оцен­ка СКл/Н) является точной и в то же время logn = o(v^).

Нелишним будет заметить, что сложность алгоритма пробных де­лений допускает оценки 0{п), 0{п^ь), 0(nlogп) и т.д., хотя, разумеет­ся, эти оценки являются более грубыми в сравнении с 0{л/п). Еще раз подчеркнем, что оценка /(n) = 0{g{n)) есть асимптотическая верхняя оценка, равно как оценка /(п) = ВДп)) — асимптотическая нижняя¹. Как, например, из Z < 5 и т < 100 нельзя вывести, что Z < т, так и из /(n) = 0{п²), g{n) = 0(,п³) нельзя вывести, что хотя бы для достаточно больших п выполняется /(n) < g{n). Оценка вида Т_А{п) = 0{g{n)) (или S_A{n) = 0{g{n))) подходит для того, чтобы «похвалить» алгоритм А, т. е. охарактеризовать его сложность как достаточно низкую (речь идет лишь об оценках вида 0{g{n)), а не о более тонких оценках, включающих символ О и имеющих вид, подобный (2.1)), но не для того, чтобы «раскритиковать» его — для таких целей скорее подой­дет оценка вида Т_А{п) = fi(h(n)). Зная, например, что сложность по числу обменов для сортировки выбором есть 0{п), а для сортировки простыми вставками — Г2(п²), мы обоснованно заключаем, что для достаточно больших п первая сложность меньше второй.

Оценки вида Т_А{п) = Q{g{n)), соединяющие в себе оценки Т_А{п) = = 0{g{n)) и Т_А{п) = fi(g(n)), в соответствующих ситуациях подходят и для характеризации сложности как сравнительно низкой, и, наобо­рот, как сравнительно высокой².

При всем этом, иногда можно услышать сообщения о новых ал­горитмах, сопровождаемые рассуждениями в духе следующего (под­разумевается, что п — размер входа): «Лучший из известных ранее алгоритмов решения этой задачи требует 0(п³) операций, а пред-

В книге [6] отмечено, что положение с символом О схоже с тем, которое возник­нет, если кто-нибудь «вместо слов „меньше чем“ начнет писать =М, например, так: 3=М(5). На вопрос: „Что значит М(5)?“ — он должен ответить: „Нечто, что мень­ше, чем 5“. Таким образом, он быстро привыкает читать М как „нечто, что меньше, чем“, приближаясь к тем самым словам, которые употребляем мы, вводя соотношение /(s)=0O(s))».

² в- и П-нотации вошли в литературу по вычислительной сложности алгоритмов с появлением статьи Д. Кнута [52], в которой автор, в частности, пишет о бессмыслен­ности нижних оценок вида 0(/(гг)) и о невозможности использования оценок такого рода как оценок сложности при сравнении алгоритмов. В [52] отмечается также, что П-нотация использовалась ранее в работах Э.Ч.Титчмарша, известного математика первой половины XX века.

22 Глава 1. Сложности алгоритмов как функции числовых аргументов

лагаемый нами алгоритм — лишь 0(п). Таким образом, достигнуто улучшение на два порядка по числу операций». Но информация, со­держащаяся в первой из этих двух фраз, не дает достаточных основа­ний для сделанного заключения. Более того, на основе этой информа­ции вообще нельзя сказать, какой из двух алгоритмов — известный ранее или новый —требует меньше операций при больших п, ведь речь идет лишь об оценках сверху, и возможно, что первая из них может быть улучшена.

Если про оценку 0(,g(n)) известно, что она точная, то это рас­ширяет возможности ее использования. Допустим, что нам известен алгоритм распознавания простоты числа п, имеющий мультиплика­тивную сложность 0(log^d п) при некотором d > 0. Тогда мультиплика­тивная сложность этого алгоритма для бесконечного множества зна­чений п (но, может быть, не для всех п) будет меньше, чем муль­типликативная сложность алгоритма пробных делений, и для этого вывода достаточно того, что сложность алгоритма пробных делений допускает точную оценку 0(л/п).

В тех случаях, когда рассматриваются два или более параметров размера входа, мы можем по-прежнему использовать асимптотиче­ские оценки вида Q{g{n₁,n₂)), где под знаком в расположена функ­ция двух переменных п₁, п₂, причем п₁, п₂ —> °°; определение в легко модифицируется на случай двух и большего числа переменных:

f{n₁,n₂) = Q{g{n₁,n₂)) <^>

"^ 3_CbC2;N>0 V_ni>„_2>N CilgCnx, n₂) | s= |/(n_l5 n₂) | s= c₂\g(n_lt n₂) |. (2.4)

То же самое сП, Оио. При этом, если имеет место оценка f{n₁, п₂) = = 0{g{n₁,n₂)), то мы назовем ее точной, коль скоро неверно, что f{n₁,n₂) = o{g{n₁,n₂)).

Утверждение, что /(п) и g{n) асимптотически эквивалентны, за­писываемое как /(n) ~g(n), означает, как известно, что /(n) = g{n) + + o(g(n)) = g(n)(l + o(l)). Утверждение, что /(n) ~ g{n), является, очевидно, более сильным, чем утверждение, что /(n) = 6(g(n)). За­метим кстати, что из формул (2.1) следует

%{п)~п², %{п)~\п² (2.5)

(например, ^(п) = п² + О(п) = п²\ + о^ = п²(1 +о(1))), но не

что

f_I (n) = n²+o(n²), f,(n) = in²+o(n²),

§ 3. Асимптотические оценки (два примера) 23

при этом из v(n) = о(п²) не следует, что v(n) = 0(п), что доказывается примером v(n) = n^3/2.

Слова «(п) имеет асимптотику g(n)» означают, что /(n)~g(n); например, 7}(п) имеет асимптотику п², а 7}(п) имеет асимптоти­ку ¹₂п².

Сложности многих алгоритмов трудно или невозможно предста­вить элементарного вида функциями от размера входа. Помимо это­го, точное значение сложности алгоритма для каждого конкретно­го значения размера входа часто не представляет особого интереса, актуальным же является исследование роста сложности при возрас­тании размера входа. Поэтому асимптотическое оценивание широко используется в теории сложности.

§ 3. Асимптотические оценки (два примера)

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

Пример 3.1.Займемся задачей построения выпуклой оболочки ко­нечного множества Мточек координатной плоскости, т. е. выпуклого многоугольника Я, содержащего все множество М(рис. 1). Множест-

Рис. 1. a) Конечное множество Мточек плоскости; б) выпуклая оболочка множества М.

во Мзадается массивом координат принадлежащих ему точек; тре­буется построить массив координат вершин многоугольника Япри обходе этого многоугольника, начиная с какой-нибудь его вершины,

24Глава 1. Сложности алгоритмов как функции числовых аргументов

против часовой стрелки (считаем, что это направление совпадает с направлением обхода точек (0,0), (1,0), (0,1), (0,0)).

Пусть n—число элементов множества M, будем считать это чис­ло размером входа. Алгоритм, основанный на переборе всех под­множеств множества M с проверкой для каждого из них, являет­ся ли оно множеством вершин искомого многоугольника H, имеет очень высокую сложность Ω(2n). Обсудим идею значительно более экономного алгоритма Р.Л.Грэхема (этот алгоритм мы обозначим буквой G).

Можно довольно быстро найти среди точек множества M такую, которая обязательно будет одной из вершин многоугольника H: до­статочно выбрать в M точку P с наименьшей ординатой, а если таких точек несколько, то из этих нескольких взять ту, которая имеет наи­меньшую абсциссу. Дополнительно найдем точку O, которая принад­лежит многоугольнику H, но не совпадает ни с одной из точек мно­жества M: возьмем для этого какие-нибудь две точки из M и найдем середину соединяющего их отрезка (если впоследствии вдруг окажет­ся, что эта точка принадлежит M, то можно будет удалить ее из M, так как она заведомо не является вершиной H).

Используя какую-нибудь сортировку с помощью сравнений, все точки множества M можно упорядочить по возрастанию углов между отрезком OP и отрезками, соединяющими O с точками множества M, при этом мы считаем, что величина каждого угла принадлежит полу­интервалу [0, 2тг). Если вдруг обнаружится, что два каких-то угла рав­ны, то упорядочим соответствующие точки по удаленности от O, но для краткости будем говорить просто о сортировке по величине угла. Соединив точки в этом порядке (будем обозначать их P_ъ P₂,..., P_n, при этом P_г = P), и соединив дополнительно P_n c P_г, мы получим замкну­тую несамопересекающуюся ломаную, но ограниченный этой лома­ной многоугольник может не быть выпуклым (см. рис. 2а). Тогда сре­ди вершин P₂,P₃, ...,P_n найдется хотя бы одна, скажем P_k , вдавленная, которая принадлежит треугольнику P_k-_гOP_k+1 при k < n и треуголь­нику P_n-₁OP₁ при k = n (рис. 2б). Вдавленную вершину можно исклю­чить из дальнейшего рассмотрения, соединив напрямую P_k-_г с P_k+1, или, соответственно, P_г с P_n-_г. Удалив все вдавленные вершины, мы получим требуемый многоугольник. Такова общая идея алгоритма. Задержимся на удалении вдавленных вершин.

¹ «Наглядно можно представлять себе дело так: в точках M вбиты гвозди, на кото­рые натянута резинка, охватывающая их все, — эта резинка и будет выпуклой оболоч­кой множества гвоздей» [21]. Но в нашем понимании построение выпуклой оболочки предполагает еще перечисление вершин в порядке их обхода.

§ 3. Асимптотические оценки (два примера)

P

P

P

P

P

P

P₁ P₁

Рис. 2. a) Точки, упорядоченные по величине угла АР₁ОР, £ = 1,2,..., п; б) вер­шина Р₄ — первая вдавленная вершина в последовательности Р₂,Р₃, ...,^8.

Вдавленные вершины можно обнаружить просмотром точек Р₂,Р₃, ...,Р_п,Р₁: переходя от вершины P_t к вершине P_i+1, i = 2,3, ... ...,п — 1, можно сразу проверять, принадлежит ли P_t треугольнику P_i_₁OP_i+1, а при переходе от Р_п к Р₁ проверять, принадлежит ли Р_п треугольнику Р_п_₁ОР₁. Если да, то P_t или соответственно Р_п, удаляет­ся, но после этого надо проверить, не окажется ли теперь вдавленной предыдущая из неудаленных вершин, — на рис. 2б видно, что после удаления Р₄ вершина Р₃ становится вдавленной. Возможно, что удале­ние одной вдавленной вершины повлечет удаление нескольких уже рассмотренных вершин, но вершина Р₁ никогда не будет удалена. При i < п — 1 после P_i+1 мы рассматриваем P_i+2

и вновь пытаемся

освободиться от вдавленных вершин с меньшими номерами и т.д. Последний шаг — переход от P_n к P₁ и завершающая попытка осво­бодиться от вдавленных вершин.

Затраты этапа построения точек P и O ограничены значением c₁n, где c₁ — некоторая константа.

Если используется сортировка, сложность которой по числу срав­нений есть r(n), то в алгоритме Грэхема может потребоваться не бо­лее c₂r(n) операций для сортировки точек по величине угла, констан­та c₂ отражает затраты на сравнение двух углов и сравнение рассто­яний от O до двух данных точек.

Покажем, что описанный процесс удаления вдавленных вершин потребует затрат, не превосходящих по величине c₃n, где c₃ —некото­рая константа (в частности, учитывающая затраты на проверку при­надлежности точки треугольнику). В самом деле, если переход от P_i к P_i+1 сопровождается проверкой вдавленности некоторого числа v_i

26Глава 1. Сложности алгоритмов как функции числовых аргументов

вершин, то число удаленных при этом вершин равно v_i — 1. Но об-

ⁿ

щее число удаленных вершин меньше n. Поэтому ^(v_i - 1) <n, и, как следствие,

ⁿ
J]v_i < 2n. (3.1)

Это означает, что сложность T_G(n) алгоритма Грэхема по общему числу арифметических операций и сравнений не превосходит c'r(n) + + c"n, где c'и c"суть некоторые положительные константы. Слож­ность любой сортировки массивов длины n по числу сравнений не может быть меньше n/2, так как каждый элемент должен пройти хо­тя бы одно сравнение и в каждом сравнении участвуют два элемента. Имеем

T_G(n) s=c'r{n) + c"n = r{n) c' + c"_r ⁿ_nт) «Sr{n)(c' + 2c"),

откуда T_G(n) = O{r{n)). При этом у нас нет пока достаточных основа­ний для утверждения, что T_с{n) = 6(r(n)), потому что нет, например, оснований утверждать, что после выбора P и O может действитель­но потребоваться r{n) сравнений обсуждаемого типа (ведь мы можем еще выполнять арифметические операции; почему бы не предполо­жить, что, прибегая к ним, можно существенно снизить число срав­нений при сортировке), и мы пока можем утверждать только то, что T_G(n) = fi(n); эту тему мы отложим до § 29.

После того как точки упорядочены по величине угла, информа­цию об их координатах можно представить в виде двунаправленно­го списка, и тогда удаление вдавленных вершин не будет связано с какими-либо перемещениями координат точек, и, подходя формаль­но, можно было бы затраты на перемещения в процессе удаления вдавленных вершин считать равными нулю. При менее формальном подходе эти затраты можно считать ограниченными сверху значени­ем cn, где c—некоторая константа: переход от массива к двунаправ­ленному списку и, равным образом, в силу (3.1), работа со ссылками во время удаления вдавленных вершин потребуют затрат, ограничен­ных величинами такого вида. В свою очередь, сложность любой сор­тировки по числу перемещений элементов не может быть меньше чем n/2 (так как не исключено, например, что изначальный поря­док элементов является обратным к требуемому). Отсюда сложность алгоритма Грэхема по числу перемещений не превосходит произве­дения некоторой константы и сложности используемой сортировки по числу перемещений. Аналогично, для сложности по общему чис-

§ 3. Асимптотические оценки (два примера)

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

Основываясь на эскизном описании алгоритма Грэхема, мы полу­чили следующее.

Для любой сортировки массивов длины n, имеющей некоторую сложность s{n) по общему числу сравнений и перемещений элемен­тов, существует алгоритм построения выпуклой оболочки n точек, заданных массивом своих координат на плоскости, сложность кото­рого по общему числу арифметических операций, сравнений и переме­щений есть O{s{n)).

Пространственная сложность алгоритма Грэхема, очевидно, есть O{n).

Пример 3.2.Пусть G = {V, E) — ориентированный граф без крат­ных ребер и v еV. Вояжем по G, выходящим из вершины v, будем называть любой путь, который

• начинается в вершине v,

• не проходит ни по одному из ребер дважды,

• завершается в вершине, из которой не выходит ни одного непрой-денного ребра

(вояж не обязательно охватывает все ребра G). Примером выходя­щего из вершины 1 вояжа в изображенном на рис. 3 графе служит (1,2,2,3,1,4).

4