Главная Промышленная автоматика. Выражение 2л не является мультипликативной функцией, но функция л является. Сделаем замену Щп) = Т(п)/2 для всех л. Тогда исходное рекуррентное перепишется в виде [/(1)= 1/2, Щп) = ЗГ7(л/2)-ь л1 Если бы Г7(1) равнялось 1, тогда однородное решение равнялось бы п° < л. Для {/(1) - 1/2 можно показать, что однородное решение не больше п/2, т.е. имеет порядок 0(л*). На частное решение значение 17(1) не влияет. Поскольку в данном случае а = 3, Ъ = 2 и t = 2.83 < а, то частное решение, а также и Щп) имеют порядок роста 0(л ). Так как Т(п) - 2Щл),то Т(п) тоже имеет порядок 0(л *), точнее 0(л°). П Пример 9.5. Рассмотрим рекуррентное уравнение Т(1) = 1, Т(п) = 2Т(л/2) -i- л logn. Легко проверить, что в данном случае однородное решение равно л, поскольку а = Ъ = 2. Но функция d(n) - п logn мультипликативной не является, поэтому надо попытаться найти значение суммы в формуле (9.16). В данном случае имеем X22*-log(2*->>-i-yl 2* 1). Так как ft = logn, то частное решение имеет порядок 0(п logn). Поскольку здесь частное решение больше однородного, то отсюда следует, что Т(п) также будет иметь порядок 0(п logn). П Упражнения 9.1. Запишите рекуррентное соотношение для времени выполнения следующего алгоритма, предполагая, что п является степенью числа 2. function path ( s/ t, n: integer ) : boolean; begin if и = 1 then if edge ( s, t) then return(true) else return(false) ; for i:= 1 to n do if pa tft(s,i,n div 2) and pa tP (i, t,n div 2) then return (true) ; return(false) end; { path } Функция edge(i,j) возврашает значение true, если вершины i и у в графе с л вершинами соединены ребром либо / ~ j, и значение false - в противном случае. Что делает функция/?а?Л (путь)? 9.2. Решите следуюшие рекуррентные уравнения, если Т(1) ~ 1. а) Т(п) = ЗТ(п/2) -i- л; б) Т(п) = ЗТ(л/2) -i- л; в) Т(п) = 8Г(л/2)-1- п. 9.3. Решите следуюшие рекуррентные уравнения, если Т(1) ~ 1. а) Т(п) = 4Г(л/2) -i- п; б) Т(п) = 4Г(л/2) + nh в) Т(п) = 9Г(л/2) -i- Л-*. 9.4. Найдите верхнюю оценку для Т(п), удовлетворяющих следующим рекуррентным уравнениям и предположению, что Т(1) = 1. а) Т(п)= Т(п/2) + 1; б) Т(п) = 2Т(п/2)+ logn; в) Т(п) = 2Т(п/2)+ п; г) Т(п)= 2Т(п/2)+ п. *9.5. Найдите верхнюю оценку для Т(п), удовлетворяющих следующим рекуррентным соотнощениям: а) = 2, Т(п) = 2Т(п -1)4-1 при л > 2. б)Г(1) = 1, Г(га)= 2Т(п - 1) -i- га при л > 2. 9.6. Проверьте ответы упражнения 9.5, рещив рекуррентные соотнощения методом подстановок. 9.7. Обобщите упражнение 9.6 для рещения произвольных рекуррентных уравнений вида Г(1)= 1. Г(га)= аТ(п - I) + d(n) при п>2 в терминах параметра а и функции d(ra). *9.8. В упражнении 9.7 положите d(ra) = с" для некоторой константы с > 1. Как в этом случае рещение Т(п) будет зависеть от соотнощения а и с? Какой вид рещения Г(га)? **9.9. Найдите Г(п),если П1) - 1, Т(п) = 4пТ(4п) + л при л > 2. 9.10. Найдите замкнутые выражения для следующих сумм: а) ±и б) ±i\ в) t2, г) ±С:. i-O ,--0 =0 iti *9.11. Покажите, что число различных порядков, в соответствии с которыми можно перемножить последовательность из л матриц, удовлетворяет следующим рекуррентным соотнощениям: Т(1) = 1, Пп) fT(i)Tin - i). I I Докажите, что Т(п+ 1) = - С," . Числа 7(га)называются числами Каталина. л + 1 " **9.12. Покажите, что число сравнений Т(п.), необходимое для сортировки л элементов посредством метода сортировки слиянием, удовлетворяет соотнощениям Т(1) = 0, Т(п)= Т([п 12]) + Щп / 2]) -ь л - 1, где [ж] обозначает целую часть числа х, а Ы - наименьщее целое, больщее или равное X. Докаките, что рещение этих рекуррентных соотнощений имеет вид Т(л) =/)("logn]-2°*"Ul. 274 ГЛАВА 9. МЕТОДЫ АНАЛИЗА АЛГОРИТМОВ 9.13. Покажите, что число булевых функций п переменных удовлетворяет рекуррентным соотношениям Ш) = 4, Т(п) = (Т(п - l)f. Найдите Г(га). **9,14. Покажите, что число двоичных деревьев высотой не более п удовлетворяет рекуррентным соотношениям Т(1) - 1, Т(п)- (T(n-l)f+ 1. Докажите, что Т(п) = для некоторой константы к. Каково значение ft? Библиографические примечания в работах [9], [44], [70] и [71] можно найти дополнительный материал по решению рекуррентных соотношений. В [4] показано, что многие нелинейные рекуррентные уравнения вида Т(п) = (Т(п - 1)) -i- g(n) имеют решения в форме Т(п) = ft" , где к - константа, как в упражнении 9.14. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 [87] 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 0.002 |