Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 20
Текст из файла (страница 20)
Для двух функций Г (и) и д (и) может не выполняться ни отношение г" (п) = 0 (д (и)), ни г" (п) = й(д(п)). Например, функции и и и1+""" нельзя асимптотически сравнивать, поскольку показатель степени в функции п|+""" колеблется между значениями О и 2 (принимая все значения в этом интервале). (и+ а) = 9 (и ) . (3.2) 3.1-3. Объясните, почему выражение "время работы алгоритма Л равно, как минимум, 0 (пз)" не имеет смысла.
3.1-4. Справедливы ли соотношения 2"+1 = 0 (2") и 2аи = О (2")? 3.1-5. Докажите теорему 3.1. 3.1-6. Докажите, что время работы алгоритма равно О (д (и)) тогда и только тогда, когда время работы алгоритма в наихудшем случае равно 0 (д (и)), а время работы алгоритма в наилучшем случае равно й (д (и)). 3.1-7. Докажите, что множество о(д(п)) Пы(д(п)) пустое. 3.1-8. Наши обозначения можно обобщить для случая двух параметров и и т, которые могут возрастать до бесконечности с разной скоростью. Для данной функции д(п, т) выражение 0 (д (и, т)) обозначает множество функций, такое что ~ (п, т): существуют положительные константы с, по и то, такие что О < Т" (п, т) < сд (и, т) для всех п > по или т > то 0(д(п,т)) = Дайте аналогичные определения обозначений П (д (и, т) ) и О (д (и, т) ).
Упражнения 3.1-1. Пусть г' (и) и д (и) — асимптотически неотрицательные функции. Докажите с помощью базового определения с1-обозначений, что гаах( Г" (п), д(п)) = Й (Г (п) + д (и)). 3.1-2. Покажите, что для любых действительных констант а и Ь, где Ь > О, справедливо соотношение Часть 1. Основы 98 В этом разделе рассматриваются некоторые стандартные математические функции и обозначения, а также исследуются взаимоотношения между ними. В нем также иллюстрируется применение асимптотических обозначений. Монотонность Функция / (и) является монотонно неубывающей (шопогошса11у шсгеаз1п8), если из неравенства т < и следует неравенство /(т) < /(и). Аналогично, функция / (и) является монотонно невозрастеющей (шопогошса11у десгеаз1п8), если из неравенства т < и следует неравенство /(т) > /(и).
Функция / (и) монотонно возрастающая (згпсг!у шсгеазш8), если из неравенства т < и следует неравенство / (т) < / (и) и монотонно убывающая (зпзсг1у г(естеаз(п8), если из неравенства т < и следует, что / (т) > / (и). Для любого действительного числа х существует наибольшее целое число, меньшее или равное х, которое мы будем обозначать как ~х1 (читается как "пол (боог) х"), и наименьшее целое число, большее или равное х, которое мы будем обозначать как 1'х1 (читается как "потолок (сей) х").
Для всех действительных чисел х — 1 < ~х1 < х < 1х1 < х + 1 (3.3) Для любого целого числа и 1'и/21 + ~и/21 = и, а для любого действительного числа и > О и натуральных чисел а и Ь справедливы следующие соотношения: Функция /(х) = ~х1 является монотонно неубывающей, как и функция / (х) = = Гх1. Модульная арифметика Для любого целого числа а и любого натурального и величина а гпос1 и представляет собой остаток от деления а на и: а шог) и = а — (а/и) и (3.8) 3.2 Стандартные обозначения и часто встречающиеся функции Округление в большую и меньшую сторону Ци/а1 /Ь1 = 1'и/аЬ1, ('1и/а3' /Ь3 = '(и/аЬ1, 1'а/Ь1 < (а+ (Ь вЂ” 1)) /Ь, (а/Ь1 > (а — (Ь вЂ” 1)) /Ь.
(3.4) (3.5) (3.6) (3.7) Глава 3. Рост функций 99 Располагая подобным определением, удобно ввести специальные обозначения для указания того, что два целых числа имеют одинаковые остатки при делении на какое-то натуральное число. Тот факт, что (а шо<1 и) = (Ь птоб и), записывается как а = Ь (шойп); при этом говорят, что число а эквивалентно, или равно числу Ь по модулю и (или что числа а и Ь сравнимы по модулю п).
Другими словами, а = Ь(тог1п), если числа а и Ь дают одинаковые остатки при делении на и. Это эквивалентно утверждению, что а = — Ь (шодп) тогда и только тогда, когда п является делителем числа Ь вЂ” а. Запись а ~ Ь(шобп) означает, что число а не эквивалентно числу Ь по модулю и. Полиномы Полинамам степени д от аргумента п называется функция р (и) следующе- го вида: в р(п) = ~~) а;и', Показательные функции Для всех действительных чисел а > О, гп н и справедливы следующие тождества: ас а а, -1 а 1/а, атп ) (а")™, Ш.~.П (а™)" (а™)" ата" Для любого и и а > 1 функция а" является монотонно неубывающей функцией аргумента и.
Для удобства будем считать, что 00 = 1. Соотношение между скоростями роста полиномов н показательных функций можно определить исходя из того факта, что для любых действительных констант где константы ао, аы..., аа — коэффициенты полинома, и ае ~ О. Полипом является асимптотически положительной функцией тогда и только тогда, когда ав > О. Для асимптотнчески положительных полиномов р (и) степени И справедливо соотношение р (и) = 6 (п~).
Для любой действительной константы а > О функция и монотонно неубывающая, а для а < О эта функция монотонно невозрастающая. Говорят, что функция Г" (и) лолнномивльно ограничена, если существует такая константа /с, что ~ (п) = О (п~). Часть 1. Основы 100 а и Ь, таких что а > 1 пь 11ш — = О аи откуда можно заключить, что пь = о (а"). Таким образом, любая показательная функция, основание а которой строго больше единицы, возрастает быстрее любой полиномиальной функции. Обозначив через е основание натурального логарифма (приблизительно равное 2.718281828...
), можем записать следующее соотношение, справедливое для любого действительного х: хз хз х1 е* = 1+х+ — + — + 2! 3! ~ 1! и=о (3.10) где символ "Г обозначает факториал, определенный ниже в этом разделе. Для всех действительных х справедливо следующее неравенство: е* > 1+х (3.1 1) Равенство соблюдается только в случае, если х = О. При ~х~ < 1 можно исполь- зовать такое приближение: 1+х<е*<1+х+х (3. 12) При х — О приближение значения функции е* величиной 1+ х вполне удовлетво- рительно: е* = 1+ х + О (хз). (В этом уравнении асимптотнческие обозначения используются для описания предельного поведения при х — О, а не при х — оо.) Для произвольного х справедливо следующее равенство: 1ш (1+Ч = * (3.13) Логарифмы Мы будем использовать следующие обозначения: Важное соглашение, которое мы приняли в книге, заключается в том, что логарифлшчески е функции применяются только к ближайшему члену выражения.
18п = 1обзп 1пп = 1оаеп 18 и = (18 п) 1818п = 18(18п) (двоичный логарифм); (натуральный логарифм); (возведение в степень); (композиция). Глава 3. Рост функций 101 Например, !к и+ й означает (1к п) + Й, а не 1я (и+ 1с). Если основание логарифма 6 > 1, то при и > О функция 1ояь и монотонно возрастает. Для всех действительных а > О, 6 > О, с > О и и выполняются следующие соотношения: 6!ояь а 1 а 1оя, (аЬ) 1обь и (3.14) (3.15) где в каждом из приведенных выше уравнений основание логарифма отлично от 1. Согласно уравнению (3.14), изменение основы логарифма приводит к умножению значения этого логарифма на постоянный множитель, поэтому мы часто будем использовать обозначение "1к п", не заботясь о постоянном множителе, как это делается в О-обозначениях.
Специалисты в области вычислительной техники считают наиболее естественной основой логарифма число 2, так как во многих алгоритмах и структурах данных производится разбиение задачи на две части. При ~х~ < 1 для функции!и (1+ х) можно написать простое разложение в ряд: хз хз х4 хь 1п(1+х) =х — — + — — — + —— 2 3 4 5 Кроме того, при х > — 1 выполняются следующие неравенства: х < 1п(1+ х) < х, 1+х (3.15) причем знак равенства имеет место только при х = О.
Говорят, что функция 1 (и) полилогарифм ически ограничена, если существует такая константа й, что 1 (и) = О (1б~ и). Соотношение между скоростью роста полиномов и полилогарифмов можно найти, подставив в уравнение (3.9) 1я и вместо и и 2а вместо а, в результате чего получим: 1аь и 1бь и 11пт 1пп — = О. а оо (2а)1ко а оо па Из приведенного выше соотношения можно заключить, что для произвольной константы а > О 1бь и = о (и').
Таким образом, любая положительная полиноми- альная функция возрастает быстрее, чем любая полилогарифмическая функция. 1окь а 1ояь (1/а) 1обь и 1ояь с 1око а + 1ока 6, п1окьа, 1ок п 1ок, Ь вЂ” 1окь и, 1 !ока 6' скжь а Часть 1. Основы 102 Факториал ы Обозначение и! (читается "и факториал") определяется для целых чисел и > 0 следующим образом: 1 при п = О, п ° (и — 1)! при п > О, т.е.и!=1 2 3 ...
и. Верхнюю границу факториала можно записать в виде п! ( и", поскольку все множители, которые определяют значение факториала, не превышают п. Однако эта оценка является грубой. Более точное приближение верхней (а также нижней) границы дает формула Стирлинго: != г ( — ) (1+9(-)) (3.17) и! = о(п"), п|= ы(2"), 18(и!) = О(п18п) (3.18) причем при доказательстве уравнения (3.18) удобно использовать формулу Стир- линга. Кроме того, для и > 1 справедливо следующее равенство: !и',„ и! = г/2ггп (-) е~" е (3.19) где (3.20) Функциональная итерация Чтобы указать, что функция у (и) последовательно г раз применяется к аргументу п, мы будем использовать обозначение 7"!г) (и).
Дадим формальное определение. Пусть функция 7" (и) задана на множестве действительных чисел. Для неотрицательных целых г можно дать такое рекурсивное определение: (г) п при г= О, г" (,г"(г ~1(и)) при г > О. и ~ ~ и ~ ~ ~ | и и г ~ ~ ~ ~ О Например, если 7" (и) = 2п, то Г"01 (и) = 2гп. где е — основание натурального логарифма. Можно доказать (см. упражнение 3.2-3), что Глава 3. Рост функций 103 Итерированная логарифмическая функция 18' и = ппп (г' > 0: 18(г! и ( 1~ . (Другими словами, 18* гг — зто минимальное число логарифмирований и, необходимое для получения значения, не превосходящего 1.) Итерированный логарифм возрастает очень медленно: 18* 2 = 1, 18* 4 = 2, 18' 16 = 3, 18' 65536 = 4, 18* (2бббзб) Поскольку количество атомов в наблюдаемой части Вселенной оценивается при- мерно в 10бс, что намного меньше, чем 2бббзб, то можно с уверенностью сказать, что входные данные такого размера гг, что 18' гг > 5, встречаются крайне редко.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
