Главная Промышленная автоматика.

Выражение 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.0037