Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 34
Текст из файла (страница 34)
ОПРЕДЕЛЕНИЕ 5.12. Пусть область определения функций Г и д — множество целых положительных чисел, а множество их значений — множество действительных чисел. Говорят, что функция д мажорирует функцию У, если существует действительное число й и целое положительное число гп такое, что ~Дп)( < й ~д(п)) для всех п > гп. Если д мажорирует г', это обозначается как У(п) = О(д(п)).
Символ О(д(п)) читается как "О большое" от д(п); при этом говорят, что г"(п) имеет порядок О большое от д(п). Для положительных целых чисел г и г следующую теорему можно доказать методом индукции. Справедливость утверждения теоремы для положительных рациональных чисел г и в можно показать, не используя логарифмы (см, упражнения). ТЕОРЕМА 5.13. Если г и з — действительные числа, г < в и и > 1, тогда и" < и'.
Следовательно, и' = О(п'). ДОКАЗАТЕЛЬСТВО. Функция 1п(х) — возрастающая, поэтому а < Ь тогда и только тогда, когда 1п(а) < 1п(Ь). Отсюда п" < и' тогда и только тогда, когда 1п(п') < 1п(п'), что, в свою очередь, выполняется тогда и только тогда, когда г1п(п) < з1п(п), т.е, тогда и только тогда, когда г < в, поскольку 1п(п) для п > 1 — величина положительная.
Следующая теорема показывает, что свойство функции иметь порядок О(д(п)) замкнуто относительно операций сложения и умножения на скаляр. Это значит, что рассматриваемые функции образуют векторное пространство, хотя изучение подобных вопросов выходит за рамки данной книги. ТЕОРЕМА 5.14. Если г(п) = 0(д(п)), то су(п) = О(д(п)). ДОКАЗАТЕЛЬСТВО. По определению, )У(п)~ < й (д(п)) для некоторого постоянного действительного числа к и всех и, больших или равных некоторому целому числу т. Поэтому (с Г(п) ! < Й )с) )д(п) ) и сГ(п) = О(д(п)).
202 ГЛАВА 5. Алгоритмы и рекурсия ТЕОРЕМА 5.15. Если г(п) = О(д(п)) и 6(п) = 0(д(п)), то (г" + 6)(п) = О(д(и)). ДОКАЗАТЕЛЬСТВО. По определению, для некоторого постоянного )с и некоторого целого числа тд имеем ~~(п)) < Ь)д(п)) для всех п > гид. Опять же по определению, для некоторой постоянной 1 и некоторого целого числа та имеем )6(п)) < 1)д(п)( для всех п > тт. Пусть т = пих(тдтг).
Следовательно, для всех п > т )у"(п) + 6(п)! < (Дп))+ )6(и)! < < й )д(и) ) + 1 )д(и) ( = = (1+1) !д(и)/ и (г" + 6)(п) = О(д(п)). ТЕОРЕМА 5.18. Если Г(п) = О(д(п)) и Ь(п) = 0(е(п)), то (Г 6)(и) = О((д.е)(п)). ДОКАЗАТЕЛЬСТВО. По определению, для некоторого постоянного Ь и некоторого целого числа тд имеем (У(п)! < Й)д(п)~ для всех и > тд. Также по определению, для некоторого постоянного 1 и некоторого целого числа та имеем )6(п)) < 1)е(п)! для всех п > тт.
Пусть т = днах(тдтг). Поэтому для всех п>т Щп) . 6(п)! = /('(п)!. /6(п)/ < < Й/д(п)/1!е(п)/ = = 61 !д(п) е(п)! и (1 6)(п) = 0((д е)(п)). Следующая теорема утверждает, что степень полинома единственным образом определяет его мажоранту. ТЕОРЕМА 5.17. Если р(п) = аьпь+аь дп" д+ + авиа+ адп+ао, то р(п) = О(п"). ДОКАЗАТЕЛЬСТВО. ~р(п)) < ~аьп" + аь дп д + . + аап + ад и + ао! < < )аьи" ) + )аь да~ ~ ) + + ~пап~ ) + )адп) + )ао! < (в силу неравенства треугольника: )А + В! < (А) + (В() < ~аь~п +)аь д)п" + .. + ~па)п + ~ад~и+ ~ао) < < !ад~ив+ ~аь дань+ '+ ~аа~ип + ~ад~и~+ (ао~иь по теореме 5.13 = ((ау,.)+ )ад д(+...
+ )аг(+ )ад)+ (ао))п' и р(п) = О(пд). ТЕОРЕМА 5.18. Для целых чисел а и Ь, больших единицы, 1оя (и) = О(1ойь(и)). РАЗДЕЛ 5.3. Сложность алгоритмог 203 ДОКАЗАТЕЛЬСТВО. Следует непосредственно из равенства 1оя,(п) = . ° 1ОКь (и) 1ок, (Ь) ТЕОРЕМА 5.19. Пусть и — неотрицательное целое число. Тогда п < 2" и, следовательно, п = 0(2").
ДОКАЗАТЕЛЬСТВО. Воспользуемся индукцией, имея для п = О, 0 < 2 = 1. Допустим, что )с < 2", тогда 1+1 < Й+)с < 2ь+ 2ь = 2. 2ь = 2~г~ и, по индукции, п < 2". Пусть Л вЂ” отношение на множестве функций со значениями во множестве целых положительных чисел, определенное как ггсд, если г"(п) = 0(д(п)). Очевидно, отношение Л рефлексивно.
Приведенная ниже теорема утверждает, что это отношение также и транзитивно. Доказательство теоремы предоставляется читателю. ТЕОРЕМА 5.20. Если ~(п) = О(д(п)) и д(п) = О(чп)), то )'(и) = О(6(п)). Следующая теорема дает ответ на вопрос о том, какие функции могут выступать в роли мажорант для других функций. ТЕОРЕМА 5.21. Для целых чисел а, больших единицы, 1ок,(п) = О(п). ДОКАЗАТЕЛЬСТВО. Согласно теореме 5.19, имеет место неравенство и < 2". Поэтому 1окз(п) < 1ояз(2") = п и 1окз(п) = О(п). Поскольку 1ок,(п) = О(1окз(п)), то по теореме 5.18 имеем 1оя,(п) = О(п).
Доказательство сформулированных ниже теорем предоставляем читателю. ТЕОРЕМА 5.22. Пусть и — неотрицательное целое число, тогда и! < и" и, следовательно, и) = О(п"). ТЕОРЕМА 5.23. Пусть а > 1 и и — неотрицательное целое число, тогда 1оя,(п1) < п1оя,(п), следовательно, 1оя,(п!) = О(п1оя (и)).
Ранее, при решении задачи о Ханойской башне, определялось число шагов, необходимых для перемещения дисков. В примере, приведенном ниже, определяется число арифметических операций, необходимых, соответственно, для сложения двух матриц и умножения двух матриц. ПРИМЕР 5.24. Рассмотрим алгоритм сложения матриц: Процедура Сложение матриц(А, В, тп, и); Цикл по г от 1 до пн ц С, =А„+В„; Конец цикла; Конец цикла; Конец процедуры.
Как видим, сложение выполняется для каждого 1 и каждого 1. Поскольку г принимает т значений, а 1 принимает п значений, то выполняется гпи операций сложения. Пусть л( = гпах(ги, п). Тогда число выполняемых арифметических операций имеет порядок 0(Ага). П 204 ГЛАВА 5. Алгоритмы и рекуроця ПРИМЕР 6.26. Алгоритм умножения матрицы А размера гп х р и матрицы В размера р х и имеет вид: Процедура Умножение матриц( А, Ю, ггь, р, п): Цикл по г от 1 до пц Цикл по г от 1 до гц Си=О; Цикл по 2 от1дор: Значение С, заменить на С; + А,ьВь,, Конец цикла; Конец цикла; Конец цикла; Конец процедуры.
Поскольку к принимает значения от 1 до р, то выполняется р операций сложения и р операций умножения. Величина )с изменяется от 1 до р для каждого г и каждого г, поэтому й пробегает значения от 1 до р тп раз. Таким образом, выполняется гпггр операций сложения и тор операций умножения. Следовательно, всего выполняется 2тпр операций.
Пусть Л = гпах(т,п,р). Тогда число выполняемых арифметических операций имеет порядок О(Агз). ьг ПРИМЕР 6.26. Сравним количество операций, которое требуется для непосредственного вычисления значения р(с), где р(х) = а„х" + а„гх" ' + . + агх + а1х+ ао, с количеством операций, которое потребуется для вычисления того же значения при помощи схемы Горнера.
Если р(с) вычисляется непосредственно, то для подсчета с" требуется выполнить й — 1 операций умножения. Еще одна операция нужна для умножения на аю так что вычисление аьс" требует й операций умножения. Таким образом, нужно выполнить 1+2+3+ . +п = -"~'-' — г) умножений. Для того чтобы найти сумму и+ 1 слагаемых, требуется выполнить п сложений, так что общее число аРифметических опеРаций Равно -"-("-г 'г + п и имеет поРЯдок О(п ). Если мы вычисляем р(а), где р(х) — полипом, используя схему Горнера, то прежде всего замечаем, что выражение а4х~+азз~+агх +а1х+ао — — х(х(т(а4х+ аз) + аг) + аг) + ао включает четыре операции сложения и четыре операции умножения. Далее мы определяем, что в общем случае р(з) = з(т(...х((а„х + а„г) + а„-г) + + аг) + а1) + ао включает п операций сложения и п операций умножения.
Таким образом, общее число арифметических операций равно 2п и имеет порядок О(п). г) ° УПРАЖНЕНИЯ 1. Сколько нужно выполнить перемещений в задаче о Ханойской башне, если число дисков равно восьми? 2. Как говорилось ранее, существует древняя легенда (начала девятнадцатого века) о том, что на один из трех бриллиантовых стержней нанизано 64 золотых диска, которые некий монах перемещает со стержня на стержень со скоростью одно движение за секунду. Согласно легенде, по окончании этой миссии наступит конец света. Как скоро это произойдет? РЯЗ4!ЕЛ 5.4. Алгоритмы сортировки 205 3.
Оцените количество арифметических операций, необходимых для вычисления указанных ниже значений полиномов (!) при непосредственном вычислении, (й) при помоши схемы Горнера. а) Г(3), где Г(х) = Зхз + 4х + 5; б) Г(2), где Г(х) = 2х4 + 4хз + Зхз + 2х + 3; в) Г(4), где Г(х) = хг+ 4х4+ 2хз+ бхз+ х+ 3. 4. Оцените количество арифметических операций, необходимых для вычисления следующих произведений: 3 0 ' б) 3 1 4 1 [ — 2 3 — 5 О]. 5 5.
Какие из приведенных ниже функций имеют порядок О(пз)? а) п4-Зп+5; б) пз — бп+5; в) (1п(п) ); г) п(1п(п)); д) п~1п(п). 6. Какие из приведенных ниже функций имеют порядок О(пз)? а) Ьпи + Зп + 2п+ 5; б) пз 1п(п); в) 1п(п"'"!"!); г) 1ой,(п!); д) и'.. 7. Пусть и — некоторое неотрицательное целое число.
Докажите, что п! < п" и, следовательно, и! = О(п"). 8. Докажите, что для а > 1 и п е )т' справедлива оценка 1оя,(п!) < п1оя (п), поэтому 1оя,(п!) = О(п1оя,(п)). 9. Докажите, что если Г(п) = О(д(п)) и д(п) = О(!4(п)), то 7(п) = О(!4(п)). 1О. Докажите, что для целого числа а, большего единицы, 1оя,(п) = О(п). 11. Используя индукцию, докажите, что если г и г — положительные целые числа, г < г и п > 1, то п" < п'. Отсюда п" = О(п'). 12. Используя результаты предыдуших задач, докажите, что для положительных рациональных чисел г и г, г < г и п > 1, из неравенства и" < и' следует, что и" = О(п').
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
