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

21

этом выполнена оценка /(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)

и¹ наоборот. Из (2.5) следует только, что

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

что

2

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