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

Для характеристики роста сложности по числу сравнений сортиров­ки простыми вставками первого и второго типа мы можем исполь­зовать известный из математического анализа символ 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. Асимптотические оценки (формализм)

19

определенных для всех достаточно больших значений п (в нашем слу­чае эти значения целые). Несимметричность записи /(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, ... Если при