Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 18
Текст из файла (страница 18)
Итерированный логарифм определяется следующим образом: 1к' п = ппп (1 > 0: 1610 и < 1~ Это очень медленно растущая функция. 1я" 2 = 1 1я' 4 = 2 1л' 16 = 3 )я" 65536 = 4 1ев!255555) Посюльку юличество атомов в видимой Вселенной оценивается примерно в 10ао, что гораздо меньше 2~~~55, мы вряд ли встретимся с входными данными размером и, таким, что 1я' п > 5, Часть 1 Основы Числа Фибоначчи Числа Фибоиаччи определяются с помощью следующего рекуррентного соотношения.
Ро =0 с'1 =1 Гс = Г$-1 + Ес-2 (3.22) для1> 2 Таким образом, каждое число Фибоначчи представляет собой сумму двух преды- дущих, что дает нам последовательность О, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 2 +1 (3.23) и задаются следующими формулами (см. упр. 3.2.6). 1+Я 2 = 1.61803 .. (3.24) 1 — Л 2 = — 0.61803 .. В частности, мы имеем ф' — ф* р;= что можно доказать по индукции (упр.
3.2.7). Поскольку ~ ф~ < 1, мы имеем откуда вытекает, что Е;= — +— (3.25) что в переводе на обычный язык гласит: "1-е число Фибоначчи Г, равно ф'/зЛ, округленного до ближайшего целого числа*'. Таким образом, числа Фнбоначчи растут экспоненциально. Числа Фибоначчи тесно связаны с залотььм сечением ф и сопряженным с ним значением ф, которые определяются уравнением Глана 5. Расе функций ат Упражнения 3.2 3 Покажите, что если функции 5" (п) и д(п) монотонно неубывающие, то таковыми же являются и функции 5"(п) + д(п) и 5(д(и)), а если вдобавок 5(п) и д(п) неотрицательны, то монотонно неубывающей является и функция 5(п) д(п).
3.2.2 Докажите уравнение (3. 16). 3.2.3 Докажите уравнение (3.19). Докажите также, что и! = ы(2") и и! = о(п"). згд * Является ли функция (1й п1! полиномиально ограниченной? А функция (1й 1л п1!? 3.2.5 * Какая из функций 1я(1я" п) и 1й" (1я п) является асимптотически большей? 3.2.6 Покажите, что золотое сечение ф и сопряженное с ним ф удовлетворяют уравнению хз = х + 1. 3.2. 7 Докажите по индукции, что зте число Фибоначчи удовлетворяет уравнению ф' — ф' Е,= где ф — золотое сечение, а ф — сопряженное с ним. з.г.в Покажите, что из к 1п к = тз(п) вьпекает я = 9(п/1п п).
Задачи 3.1. Асимптотическое поведение полииамов Пусть р(п) = 2 а;и', з=о где ае > О, представляет собой полинам степени Ы от п, и пусть )с является константой. Используя определения асимптотических обозначений, докажите следующие свойства. а Если я > д, тор(п) = 0(п"). Часть 1 Осаавы вб б. Если к < с),тор(п) = Й(п"). в. Если lс = Н, то р(п) = св(пь). * Если )с > Н, то р(п) = о(п"). д. Если к < Ы, то р(п) = ы(п"). 3.2. Относительный асимитотическийрост Для каждой пары приведенных в таблице выражений (А, В) укажите, каким отношением А связано с В: О, о, Й, ы или 9. Предполагается, что )с > 1, в > О и с > 1 — константы. Ваш ответ должен выражаться таблицей, в каждой ячейке которой указано значение "Да" или "Нет". 3.3.
Упорядочение по скорости асимитотического роста а. Расположите приведенные ниже функции по скорости их асимптотического роста, т.е. постройте такую последовательность функций дпдз,...,дзо, что дг = Й(дз) дз = Й(дз),, дзз = Й(дзо). Разбейте свой список на классы эквивалентности так, чтобы функции 1"(п) и д(п) находились в одном и том же классе тогда и только тогда, когда 1"(п) = ~Э(д(п)). (,/г)' " 1зп пз (1й п)! пй'в" 2з" 1б(п1) п~я1 " 4'Я" (п+ 1)1 чЯ й 2'Я" еа в1 1к" (1к п) б. Приведите пример неотрицательной функции 1(п), такой, что для всех функций д,(п) из части (а) 1(п) не принадлежит ни множеству 0(д;(и)), нн множеству Й(д (п)). 3.4. Свойства асимптотическик обозначений Пусть |(п) и д(п) — асимптстнчески положительные функции. Докажите или опровергните справедливость каждого из приведенных ниже утверждений.
1й(1й' п) (з)а 1п1пп 1б' п (1 )1ва 2" ~1я" Пааво 3. Рост функций а. Из у(п) = 0(д(п)) вытекает д(п) = 0(у(п)). б. 1(п) + д(п) = 9(ш)п()'(п), д(п))). в. Из Дп) = О(д(п)) вытекает!й(Дп)) = О(1я(д(п))), где 1к(д(п)) > 1 и у(п) > 1 для всех достаточно больших п. г. Из 1(п) = 0(д(п)) вытекает 2У1"1 = О (2в1"1). д. 1(п) = ОЯ(п))з). е Из )(и) = 0(д(п)) вытекает д(п) = й(1(п)). ж г"(п) = 9®п/2)). з. 1(п) + оЦ(п)) = Й(у(п)). 3.5.
Вариации алределений О и й Некоторые авторы определяют й несколыю иначе, чем это делали мы; давайте для такого альтернативного определения будем использовать символ Й (читается как "омега бесконечность" ). Будем говорить, что 1(п) = 1с(д(п)), если существует положительная константа с, такая, что 1" (п) > сд(п) > 0 для бесконечного количества целых чисел п.
а Покажите, что для любых двух асимптотически неотрицательных функций у(п) и д(п) выполняется одно из соотношений 1'(п) = 0(д(п)) и У(п) = 1с(д(п)) (или они оба), в то время как при использовании й вместо 1с зто утверждение ложно, й Опишите потенциальные преимущества и недостатки применения 11 вместо й для характеристики времени работы программ. Некоторые авторы определяют несколько иначе и О; для такого альтернативного определения будем использовать символ 0'. Будем говорить, что 1" (п) = 0'(д(п)) тогда и только тогда, когда ~У(п) ~ = 0(д(п)).
в. Что произойдет в теореме 3.1 с каждым из направлений "тогда и только тогда, когда", если заменить 0 на 0', но оставить без изменений й? Некоторые авторы определяют О (читается как "о с тильдой") для обозначения О, в котором игнорируются логарифмические множители: 0(д(п)) = (У(п): существуют положительные константы с, к и по, такие, что О < у (и) < сд(п) ай(п) для всех п > по), г, Определите Й и Й аналогичным образом.
Докажите соответствующий аналог теоремы 3.1. Часть т Основы З.б. Итернрованные функции Оператор итерации *, используемый в функции 18', можно применить к любой монотонно возрастающей функции 1'(и), определенной на множестве действительных чисел. Для заданной константы с Е И итерированная функция Д определяется следующим образом: [с (и) = ппп [е' > 0: г(0(п) ( с) Она может не быть вполне определенной во всех случаях. Другими словами, величина Д,*(п) представляет собой количество итерированных применений функции г", требующееся для того, чтобы уменьшить ее аргумент до значения, не превышающего с. Для каждой из приведенных далее функций г(п) и констант с дайте максимально точную оценку функции Д;(п). Заключительные замечания Кнут (Кпиб2) [208]з попытался выяснить происхождение О-обозначений и обнаружил, что впервые они появились в 1892 году в учебнике П.
Бахманна (Р. ВасЬ- гпапп) по теории чисел. О-обозначения были введены в 1909 году Э. Ландау (Е. Еаш[ап) при обсуждении распределения простых чисел. Введение П- и еЭ-обозначений приписывают Кнуту [212), который исправил неточность популярного в литературе, но технически неаккуратного применения О-обозначений как для верхней, так и для нижней асимптотических границ. Многие продолжают использовать О-обозначения там, где более уместны были бы В-обозначения.
Дальнейшее обсуждение исторического развития асимптотических обозначений можно найти у Кнута [208, 2121, а также Брассарда (Вгаааап1) и Брейтли (Вгабеу) [53). Определения асимптотических обозначений у разных авторов иногда различаются, однако в большинстве часто встречающихся ситуаций они дают согласу- лныеется русский иереяси Д. Кнут. Искусство нрограммнровання. т. ! Основные алгоритмы.
З.е ила— Мл И.д. "Вильямст 2ИЮ. В9 Глана я Рост функиий ющиеся результаты. В некоторых альтернативных случаях подразумевается, что функции не являются асимптотически неотрицательными, поэтому ограничению подлежит их абсолютное значение. Равенство (3.20) было получено Роббинсом (КоЬЬ(па) 1295]. Другие свойства элементарных математических функций можно найти в любом хорошем справочнике по математике, например, в справочнике Абрамовича (АЬгашоМгсЬ) и Стеган (81еуш) [1] или Цвиллингера (Еяс(П)пйег) 1360], а также в книгах по вычислительной математике, таких как книги Апостола (Аромо1) 118] или Томаса (ТЬошаз) и др.
(332]. В книгах Кнута 1208], а также Грехема (СагаЬаш), Кнута и Паташника (Ра1азЬпйс) (151]4 содержится множество материала по дискретной математике, который используется в информатике. анмтнся Русский перевод: К Грякем, д. Кнут, О. Паташннк. Конкретное математика. Мотеиатннаскне осноаы инфарктники, 2-е иза — Мс И.Д. "Вивавмс", 20!О. Глава 4. Разделяй и властвуй В разделе 2.3.1 вы познакомились с применением парадигмы "разделяй и властвуй" на примере сортировки слиянием.
Напомним, что при данном подходе мы решаем задачу рекурснвно, применяя на каждом уровне рекурсии три шага. Разделение задачи на несколько подзадач, которые представляют собой меньшие экземпляры той же задачи. Властвование над подзадачами путем их рекурсивного решения. Если размеры подзадач достаточно малы, такие подзадачи могут решаться непосредственно. Комбинирование решений подзадач в решение исходной задачи.
Если подзадачи достаточно велики для рекурсивного решения, мы называем эту ситуацию рекувснвным случаем. Если подзадачи становятся достаточно малы для того, чтобы не прибегать к рекурсии, мы говорим, что рекурсия "достигает дна" и опускается до базового случая. Иногда, в дополнение к подзадачам, которые представляют собой меньшие экземпляры той же задачи, приходится решать подзадачи, несколько отличающиеся от исходной задачи. Мы рассматриваем решение таких подзадач как часть шага комбинирования.
В этой главе мы рассмотрим новые алгоритмы, основанные на подходе "разделяй и властвуй". Первый из них решает задачу максимального подмассива: на вход алгоритма поступает массив чисел, и необходимо найти непрерывный подмассив, значения которого дают наибольшую сумму. Затем мы рассмотрим два алгоритма "разделяй н властвуй", предназначенные Лля умножения матриц размером п х п.
Один из них имеет время работы ~Э(п ), что не лучше, чем время работы обычного алгоритма непосредственного умножения, но второй, алгоритм Штрассена, выполняет умножение за время 0(п~.~~), так что он асимптотически лучше, чем алгоритм непосредственного умножения. Рекуррентные соотношения Рука об руку с парадигмой "разделяй и властвуй" идут рекуррентные соотношения, поскольку онн предоставляют естественный способ описания времени работы соответствующих алгоритмов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
