Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 17

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 17)

Однако одно из свойств действительных чисел в асимптотических обозначениях не выполняется. Трнхотомия Для любых двух действительных чисел а и Ь должно выполняться толью одно из соотношений а < Ь, а = Ь и а > Ь. Упражнения 3.1.1 Пусть 3'(п) и д(п) — асимптотически неотрицательные функции. Докажите с по- мощью базового определения 6-обозначений, что шах®п), д(п)) = 6(3'(вл) + д(п)).

3.1.2 Покажите, что для любых действительных констант а н Ь, где 6 > О, выполняется соотношение (и+ а) = сл(п ) . (3.2) 3.1.3 Поясните, почему утверждение "время работы алгоритма А равно как минимум О(п )'* лишено смысла. 3.1.4 Справедливы ли соотношения 2"'"1 = О(2") и 2зи = О(2")? 3.1.5 Докажите теорему ЗА. Хотя можно сравнивать любые два действительных числа, в отношении асимптотнческого сравнения функций это утверждение не является справедливым. Для двух функций 3 (и) и д(п) может не выполняться ни отношение 1(п) = 0(д(п)), ня отношение 3'(и) = Й(д(п)). Например, нельзя асимптотически сравнивать функции п и п'"'"", поскольку показатель степени в функции п1+""" колеблется между значениями О и 2, принимая все значения в этом интервале. Часть 7 Основы 3.1.6 Докажите, что время работы алгоритма равно б!(д(п)) тогда и только тогда, когда его время работы в наихудшем случае равно О(д(п)), а в наилучшем — Й(д(п)). 3.1.7 Докажите, что множество о(д(п)) П ю(д(п)) является пустым.

3.1.8 Можно обобщить наши обозначения на случай двух параметров п и гп, которые могут возрастать до бесконечности по отдельности с разными скоростями. Для данной функции д(п, т) обозначим как 0(д(п, т)) множество функций 0(д(п, т) ) = (1(п, т): существуют положительные константы с, по и то, такие, что 0 < 1(п, т) < сд(п, т) для всех п > по или т > то) .

Приведите соответствующие определения для 11(д(п, т)) и 6(д(п, т)). 3.2. Стандартные обозначения и часто встречающиеся функции В атом разделе рассматриваются некоторые стандартные математические функции и обозначения, а также исследуются взаимоотношения между ними. В нем, кроме того, иллюстрируется применение асимцтотических обозначений. Монотонность Функция 3'(п) является монотонно неубывающей (пюпо1ошсайу )псгеагйпй), если из т < п вытекает 1(т) < )'(п). Аналогично она является монотонно нввозрвсювющей (шопо1ошса11у бесгеаа(пй), если из т < п вытекает 1(т) > 1(п). Функция 1" (п) является монотонно возрастающей (яП(с11у (псгеав)пй), если из т < п вытекает У(т) < 1(п), и монотонно убывающей (вптсг!у десгеав)пй), если из т < п вытекает 1(т) > 3'(п).

Полы и потолки Для любого действительного числа х обозначим наибольшее целое число, меньшее или равное х, как (х) (читается как "пол (11оог) х"), а наименьшее целое число, большее или равное х, — как !"х1 (читается как "потолок (се(!) х"). Для всех действительных х х — ! < ~х~ < х < (х1 < х+1. (3.3) Для любого целого п (п/21 + 1п/21' = п, Глава 3. Рост функций 79 а для любого действительного числа х > 0 и целых чисел а, 6 > О, Г*/ 1 Ь (х/а) Ь (3.4) (3.5) га1 а+ (6 — 1) Ь Ь ~а~ а — (6 — 1) (З.б) (3.7) Модульнан арифметика Для любого целого числа а и любого натурального и величина а пюй и представляет собой остаток от деления а на и: а пюй п = а — п (а/п) (3.8) Отсюда следует, что О < а щой и < п .

(3.9) Располагая подобным определением, удобно ввести специальные обозначения для указания того, что два целых числа имеют одинаковые остатки при делении на каюе-то натуральное число. Тот факт, что (а шоб и) = (6 пег( и), записывается как а = 6 (шод и); при этом говорят, что число а эквивалентно, или равно, числу 6 по модулю и (или что числа а и 6 сравнимы по модулю и). Другими словами, а = Ь (пюс) и), если числа а и 6 дают одинаковые остатки при делении на и. Это эквивалентно утверждению, что а = Ь (шоб и) тогда и только тогда, когда п является делителем числа Ь вЂ” а.

Запись а ф Ь (пюг( и) означает, что число а не эквивалентно числу 6 по модулю и, Полиивмы Для заданного неотрицательного целого д полиномом степени и' от аргумента п называется функция р(п) вида И р(п) ~~~ а ~п' где константы ао, ам ., ., ав — коэ44нцненты полинома и ав ф О. Полинам является асимптотическн поломаггельной функцией тогда и только тогда, когда ав > О. Для асимптотически положительных полиномов р(п) степени д справедливо соотношение р(п) = 6(пв). Для любой действительной константы а > 0 функция и' монотонно неубывающая, а для а < 0 эта функция монотонно невозраста- Функция /(х) = (х~ является монотонно неубывающей, как и функция У(х) = Гх1.

во Часнь 1 Основы Показательные функции Для всех действительных чисел а > О, ги и и справедливы следующие тождества. а =1 а =а а =1/а (а )" = а " (а )" = (а") аы+п Для всех п и а > 1 функция а" является монотонно неубывающей функцией аргумента и. Для удобства будем считать, что Ос = 1. Соотношение между скоростями роста полиномов и показательных функций можно определить исходя из того факта, что для любых действительных констант а и 6, таких, что а > 1, пь 1пп — = О, -н а" откуда можно заключить, что и = о(а") .

(3.10) Таким образом, любая показательная функция, основание а которой строго больше единицы, возрастает быстрее любой полиномиальной функции. Обозначив через е основание натурального логарифма (приблизнтельно равное 2.718281828... ), можем записать следующее соотношение, справедливое для любого действительного х: х е* = 1+х+ — + — + 2! 3! ~- 1! ' с=о (3.11) где "Г' обозначает факториал, определенный ниже в зтом разделе.

Для всех дей- ствительных х справедливо следующее неравенство: е*>1+х (3.12) где равенство выполняется только при х = О. Когда ~х~ < 1, можно использовать такое приближение: 1+х < е* < 1+х+х (3.13) При х — э 0 приближение е* функцией 1 + х вполне удовлетворительно: е* = 1+ х+ 9(х ) ющая. Говорят, что функция У(п) полннаннааьно ограничена, если существует такая константа )с, что 7" (п) = О(пь).

Главе 3. Рост функяий В этом уравнении асимптотические обозначения используются для описания пре- дельного поведения при х -ь О, а не при х ь оо. Для всех х мы имеем 1пп (1+ — ) = е*. (3.14) Логарифмы Мы будем использовать следующие обозначения. 1$ и = 10$з и 1пп = 1олсп 1бьп = (1ба)ь 151бп = 1й(1бп) (бинарный логарифм) (натуральный логарифм) (возведение в степень) (композиция) Ькжь с 1ол,а+ 1ол, Ь, п10$ь а, 1ол, а 1об, Ь вЂ” 1обь а, 1 1ОК смаь а 1ок,(аЬ) 1оль а" 1ойь а (3.15) 1обь(1/а) 1обь а аыеь с (3.16) где в каждом из приведенных уравнений основание логарифма не равно 1.

Согласно уравнению (3.15) изменение основания логарифма приводит к умножению значения этого логарифма только на постоянный множитель, поэтому мы часто будем использовать обозначение "1я и", не заботясь о постоянном множителе, как это делается в О-обозначениях. Специалисты в области вычислительной техники считают наиболее естественной основой логарифма число 2, так как во многих алгоритмах и структурах данных производится разбиение задачи на две части. При ~х~ ( 1 имеется простое разложение в ряд хз хз 1п(1+ х) — х + х4 хь 4 5 Важное соглашение, которое мы приняли в книге, — логарифмические функиии нрименяютея только к ближайшему члену выражения.

Например, (бп + к означает (1кп) + )с, а не 1л(п+ )с). Если основание логарифма 6 > 1, то при и > О функция 1окь п монотонно возрастает. Для всех действительных а > О, Ь > О, с > О и и часть я Основы Кроме того, для х > — 1 выполняются следующие неравенства: < 1п(1+х) < х, 1+х (3.17) где равенство достигается только при х = О. Говорят, что функция Дп) иолилогарифмически ограничена, если существует такая константа !с, что у(и) = О(18~ и).

Соотношение между скоростью роста полиномов и полилогарифмов можно найти, подставив в уравнение (3.10) 18п вместо и и 2' вместо а, в результате чего получим 1 ьп 1 ьп 1пп = 1пп — = 0 н-всс (2а)!ан н-+сс п!' Таким образом, любая положительная полиномиальная функция возрастает быст- рее, чем любая полилогарифмическая функция. Факториалы Обозначение и! (читается как "и факториал") определено для целых чисел п > 0 следующим образом: 1, если и = О, и! = п (п — 1)!, если п > 0 .

Таким образом, и! = 1 2 3 и. Слабой верхней границей факториала является п! < и", поскольку каждый из и членов, входящих в факториальное произведение, не превышает п. Формула Со!ирл мига, и! = ъ~2~гп ( — ) (1 + !В ( — ) ) (3.18) где е — основание натуральных логарифмов, дает более точную верхнюю (а также нижнюю) границу. В упр. 3.2.3 требуется доказать, что и! = о(п"), и! — ! ~(2н) 18(п!) = тт(п18п), (3.19) причем при доказательстве уравнения (3.19) удобно использовать формулу Стир- линга.

Для всех и > 1 справедливо также следующее равенство: и! = ч!2яп ( — ) е~", е (3.20) Из приведенного выше соотношения можно заключить, что для произвольной константы а > 0 18 п=о(п). Вл Глава 3. Рост функций (3.21) Функциональная итерация Запись ~10(п) используется для обозначения функции Дп),итеративно примененной ! раз к исходному значению и.

Подходя формально, пусть Дп) является функцией от действительного аргумента. Для неотрицательных целых ! рекурсивно определим п, если!=0, ЩО ')(и)), если ! > 0 . Например, если У(п) = 2п, то у!0(п) = 2'и. Итернрованная логарифмическая функция Обозначение !я' п (читается как "логарифм со звездочюй от и") будет применяться для указания повторно применяемого логарифма, который определяется следующим образом. Пусть 1610 и представляет собой итерацию функции )'(п) = !я и. Посюльку логарифм от отрицательных чисел не определен, функция 1601 п определена, только если 160 ~) п > О. Не перепутайте обозначения 1610 и (логарифм, примененный последовательно 4 раз к аргументу и) и 1я' и !логарифм и, возведенный в 1-ю степень).

Характеристики

Список файлов книги