Алгоритмы - построение и анализ (1021735), страница 19
Текст из файла (страница 19)
Аналогично, функция / (и) является монотонно невозрастеющей (шопогошса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, встречаются крайне редко.
Числа Фибоначчи Числа Фибоначчи определяются с помощью следующего рекуррентного соотношения: Го = О, Е, = 1, Рг = Р; г+ Гг з, г > 2. (3.21) Таким образом, числа Фибоначчи образуют последовательность, в которой каждое очередное число представляет собой сумму двух предыдущих: О, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, Обозначение !к* и (читается как "логарифм со звездочкой от и") будет применяться для указания повторно применяемого логарифма, который определяется следующим образом.
Пусть 18(г! и представляет собой итерацию функции Г" (и) = = 18 и. Поскольку логарифм от неотрицательных чисел не определен, то функция 180! п определена, только если 18(г ~! гг > О. Не перепугайте обозначения 18(г! гг (логарифм, примененный последовательно г раз к аргументу и) и 1бг и (логарифм и, возведенный в г-ую степень). Итерированный логарифм определяется следующим образом: Часть 1. Основы 104 Числа Фибоначчи тесно связаны с золоюиым сечением ф и сопряженным значе- нием Ф, которые задаются следующими формулами: = 1.б1803...
2 = — 0.51803 .. 2 (3.22) В частности, справедливо такое соотношение: Ф' — Ф Р;= (3.23) Упражнения 3.2-1. Покажите, что если функции / (и) и д (и) — монотонно неубывающие, то функции /(и) + д(п) и /(д(п)) также монотонно неубывающие. Кроме того, если к тому же функции /(и) и д (и) — неотрицательные, то монотонно неубывающей является также функция / (и) . д (и). 3.2-2. Докажите уравнение (3.15). 3.2-3. Докажите уравнение (3.18). Кроме того, докажите, что кй = ы (2") и и1 = = о(п"). * 3.2-4. Является ли функция (18 п1! полиномиально ограниченной? Является ли полиномиально ограниченной функция (18 18 п1? *3.2-5. Какая из функций является асимптотически ббльшей: 18(18*п) или 18* (18 и)? 3.2-6. Докажите методом математической индукции, что 1-е число Фибоначчи удовлетворяет следующему равенству: Ф' — Ф' Г;= где Ф вЂ” золотое сечение, а Ф вЂ” его сопряженное. 3.2-7.
Докажите, что при 1 > 0 (1+ 2)-ое число Фибоначчи удовлетворяет нераВенству Е~-~-з ) Ф'. которое можно доказать методом индукции (см. упражнение 3.2-6). Поскольку Г Ф( < 1, то выполняются неравенства )Ф')/~/5 < 1/~/5 < 1/2. Таким образом, г'-е число Фибоначчи Г, равно Ф'/~/5, округленному до ближайшего целого числа. Следовательно, числа Фибоначчи возрастают как показательная функция. 105 Глава 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
