Структуры данных и алгоритмы (1021739), страница 71
Текст из файла (страница 71)
В первом примере получаем небольшое обобщение мультипликативных функций, а именно, здесь рассматриваются мультипликативные функции, умноженные на константу, которая больше или равна единице. Вовтором примере просто показан частный случай функции d(n), позволяющий получить замкнутую форму решения (9.16).Пример 9.4. Рассмотрим следующее рекуррентное уравнение:Т(1) = 1,Т(п) = ЗГ(л/2) + 2л1-5.272ГЛАВА 9. МЕТОДЫ АНАЛИЗА АЛГОРИТМОВВыражение 2л1'5 не является мультипликативной функцией, но функция л1'5 является. Сделаем замену Щп) = Т(п)/2 для всех л. Тогда исходное рекуррентное перепишется в видеЩ1) = 1/2,Щп) = ЗЩп/2) + л1-5.Если бы Щ1) равнялось 1, тогда однородное решение равнялось бы л'083 < л1'59.
ДляЩ1) — 1/2 можно показать, что однородное решение не больше л1'59/2, т.е. имеет порядок О(п1'59). На частное решение значение Щ1) не влияет. Поскольку в данном случаеа = 3, Ъ = 2 и б1'5 = 2.83 < а, то частное решение, а также и Щп) имеют порядок ростаО(п1-59). Так как Т(п) — 2Щп), то Т(п) тоже имеет порядок О(л1'59), точнее О(л1ов3). ППример 9.5. Рассмотрим рекуррентное уравнениеТ(1) = 1,Т(п) = 2Т(л/2) + л logn.Легко проверить, что в данном случае однородное решение равно л, посколькуа = Ъ = 2.
Но функция d(n) — п logn мультипликативной не является, поэтому надопопытаться найти значение суммы в формуле (9.16). В данном случае имеем*-i1*-i1V1поуо*-А_ o*V(Ъ —J)i\—— £t9*" K\Kb(bT^j- J.J.1\/ Ctnink-j£tlUgl^) —Ct / \Ki=oj=otТак как ft = logn, то частное решение имеет порядок О(п Iog2n). Поскольку здесьчастное решение больше однородного, то отсюда следует, что Т(п) также будет иметьпорядок О(л Iog2n). ПУпражнения9.1.9.2.Запишите рекуррентное соотношение для времени выполнения следующего алгоритма, предполагая, что п является степенью числа 2.function path ( s/ t, n: integer ) : boolean;beginif n = 1 thenif edge(s, t) thenreturn(true) telsereturn(false);for i:= 1 to n doif path(s,i,n div 2 ) and path(i,t,n div 2) thenreturn(true);return(false)end; { path }Функция edge(i, j) возвращает значение true, если вершины i и у в графе с лвершинами соединены ребром либо i = j, и значение false — в противном случае.
Что делает функция path (путь)?Решите следующие рекуррентные уравнения, если Т(1) = 1.а) Т(п) = ЗГ(п/2) + л;б) Т(п) = ЗГ(л/2) + л2;39.3.в) Т(п) = 8Т(п/2) + п .Решите следующие рекуррентные уравнения, если Т(1) = 1.а) Т(п) = 4Г(л/2) + п;б) Т(п) = 4Т(л/2) + л2;3в) Т(п) = 9Г(л/2) + л .УПРАЖНЕНИЯ9.4.*9.5.9.6.9.7.Найдите верхнюю оценку для Т(п), удовлетворяющих следующим рекуррентным уравнениям и предположению, что Т(1) = 1.а) Т(п) = Г(л/2) + 1;б) Т(п) = 2Т(п/2) + logn;в) Т(п) = 2Т(п/2) + п;г) Т(п) = 2Т(п/2) + п2.Найдите верхнюю оценку для Т(п), удовлетворяющих следующим рекуррентным соотношениям:а) Г(1) = 2,Т(п) = 2Т(п - 1) + 1 при л > 2.б) Г(1) = 1,Т(п) = 2Т(п - 1) + га при л > 2.Проверьте ответы упражнения 9.5, решив рекуррентные соотношения методомподстановок.Обобщите упражнение 9.6 для решения произвольных рекуррентных уравнений видаТ(п) = аТ(п - 1) + d(n) при п £ 2в терминах параметра а и функции d(n).*9.8.
В упражнении 9.7 положите d(n) = с" для некоторой константы с > 1. Как вэтом случае решение Т(п) будет зависеть от соотношения а и с? Какой вид решения Г(л)?**9.9. Найдите Т(п), если7XD - 1,Г(л) = VnT(>//z) + л при л > 2.9.10. Найдите замкнутые выражения для следующих сумм:a)£i. б)£Л в)i=0i=0*9.11. Покажите, что число различных порядков, в соответствии с которыми можноперемножить последовательность из л матриц, удовлетворяет следующим рекуррентным соотношениям:Т(1) = 1,Докажите, что Т(п + 1) = - С," .
Числа Т,(п) называются числами Катпалана.л+1 '**9.12. Покажите, что число сравнений Т(п), необходимое для сортировки л элементовпосредством метода сортировки слиянием, удовлетворяет соотношениямГ(1) = О,Т(п) = Т([п 1 2]) + Т(\ п 1 2]) + л - 1,где [ж] обозначает целую часть числа х, а Ы — наименьшее целое, большее илиравное х. Докажите, что решение этих рекуррентных соотношений имеет вид274ГЛАВА 9. МЕТОДЫ АНАЛИЗА АЛГОРИТМОВ9.13. Покажите, что число булевых функций п переменных удовлетворяет рекуррентным соотношениям= 4,2Т(п) = (Т(п - I)) .Найдите Т(п).**9.14. Покажите, что число двоичных деревьев высотой не более п удовлетворяет рекуррентным соотношениям- 1,2Т(п) - (Т(п - I)) + 1.2Докажите, что Т(п) = А "для некоторой константы k.
Каково значение ft?Библиографические примечанияВ работах [9], [44], [70] и [71] можно найти дополнительный материал по решению рекуррентных соотношений. В [4] показано, что многие нелинейные рекуррент22ные уравнения вида Т(п) = (Т(п - I)) + g(n) имеют решения в форме Т(п) = ft " ,где k — константа, как в упражнении 9.14.•УПРАЖНЕНИЯ275ГЛАВА 10МетодыразработкиалгоритмовК настоящему времени специалисты по вычислительной технике разработали рядэффективных методов, которые нередко позволяют получать эффективные алгоритмы решения больших классов задач.
Некоторые из наиболее важных методов,такие как "разделяй и властвуй" (декомпозиции), динамическое программирование, "жадные" методы, поиск с возвратом и локальный поиск, представлены в этойглаве. Пытаясь разработать алгоритм решения той или иной задачи, часто бываетполезно задать вопрос: "Какой тип решения позволяет получить метод декомпозиции, динамическое программирование, "жадный" метод или какой-либо другойстандартный метод?"Следует, однако, подчеркнуть, что существуют задачи, например NP-полные задачи, для которых эти и любые другие известные методы не обеспечивают эффективных решений. Когда встречается подобная задача, нередко бывает полезно определить, обладают ли входные данные для этой задачи какими-либо особыми характеристиками, которыми можно воспользоваться при попытках найти требуемоерешение, и можно ли воспользоваться каким-либо приближенным решением (еслитакое решение легко получить) вместо точного решения, получить которое бываеточень трудно.10.1.
Алгоритмы „разделяй и властвуй"Возможно, самым важным и наиболее широко применимым методом проектирования эффективных алгоритмов является метод, называемый методом декомпозиции(или метод "разделяй и властвуй", или метод разбиения). Этот метод предполагаеттакую декомпозицию (разбиение) задачи размера п на более мелкие задачи, что наоснове решений этих более мелких задач можно легко получить решение исходнойзадачи. Мы уже знакомы с рядом применений этого метода, например в сортировкеслиянием или в деревьях двоичного поиска.Чтобы проиллюстрировать этот метод, рассмотрим хорошо известную головоломку"Ханойские башни".
Имеются три стержня А, В и С. Вначале на стержень А нанизаны несколько дисков: диск наибольшего диаметра находится внизу, а выше — дискипоследовательно уменьшающегося диаметра, как показано на рис. 10.1. Цель головоломки — перемещать диски (по одному) со стержня на стержень так, чтобы дискбольшего диаметра никогда не размещался выше диска меньшего диаметра и чтобы вконце концов все диски оказались нанизанными на стержень В. Стержень С можноиспользовать для временного хранения дисков.Для решения этой головоломки подходит следующий простой алгоритм. Представьте, что стержни являются вершинами треугольника.
Пронумеруем все перемещения дисков. Тогда при перемещениях с нечетными номерами наименьший дискнужно перемещать в треугольнике на соседний стержень по часовой стрелке. Приперемещениях с четными номерами выполняются другие допустимые перемещения,не связанные с наименьшим диском.БС1Рис. 10.1. Исходное положение в головоломке "Ханойские башни"Описанный выше алгоритм, конечно, правильный и, к тому же, весьма лаконичный, правда, нелегко понять, почему он "работает", да и вряд ли такой алгоритм быстро придет вам в голову.
Попробуем вместо этого применить метод декомпозиции. Задачу перемещения п наименьших дисков со стержня А на стержень В можно представитьсебе состоящей из двух подзадач размера п — 1. Сначала нужно переместить п — 1 наименьших дисков со стержня А на стержень С, оставив на стержне А п-А наибольшийдиск.
Затем этот диск нужно переместить с А на В. Потом следует переместить п - 1дисков со стержня С на стержень В. Это перемещение га - 1 дисков выполняется путемрекурсивного применения указанного метода.1 Поскольку диски, участвующие в перемещениях, по размеру меньше тех, которые в перемещении не участвуют, не нужнозадумываться над тем, что находится под перемещаемыми дисками на стержнях А, Вили С.
Хотя фактическое перемещение отдельных дисков не столь очевидно, а моделирование вручную выполнить непросто из-за образования стеков рекурсивных вызовов, с концептуальной точки зрения этот алгоритм все же довольно прост для понимания и доказательства его правильности (а если говорить о быстроте разработки, тоему вообще нет равных). Именно легкость разработки алгоритмов по методу декомпозиции обусловила огромную популярность этого метода; к тому же, во многих случаях эти алгоритмы оказываются более эффективными, чем алгоритмы, разработанные Традиционными методами.2',.'•..."•••'••.'•':•' 'V•- ••'Умножение длинных целочисленных значенийРассмотрим задачу умножения двух п-битовых целых чисел X и Y. Вспомним,что алгоритм умножения га-битовых (или га-разрядных) целых чисел, изучаемый всредней школе, связан с вычислением п промежуточных произведений размера п ипоэтому является алгоритмом О(п2), если на каждом шаге выполняется лишь умножение или сложение одного бита или разряда.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
