Валенсия

Испания

Лабораторная работа 2. Рекуррентные уравнения.
 [b]Задание 1[/b]. Решить следующие рекуррентные уравнения:
     1) T( n) =4T(2n/3) + 1, T(1) = 3
         T( n) = T(n-1) + lg n, T(1) = 4
         T( n) = T(n/3) + T(3n/5) + n
     2) T( n) = T(n-1) + n2, T(1) = 1
         T( n) = 3T(3n/4) + n, T(1) = 1
         T( n) = T(n/6) + T(3n/4) + n2
        
 [b]Задание 2.[/b] Определите верхнюю и нижнюю асимптотические границы функции T( n) для каждого из перечисленных ниже рекуррентных соотношений. Считаем, что T( n) - константа при достаточно малых n. Обоснуйте свой ответ.
    1) T( n) = 2T(n/2) + n3 
        T( n) = 7T(2n/5)+n2 
        T( n) = 2T(n/4) +n1/2
 
    2) T( n) = T(9n/10) + n 
        T( n) = 6T(n/2) + n2 
        T( n) = 16T(n/4) + n2
 [b]Задание 3*[/b]. Решить следующее рекуррентное уравнение: 
 T( n)=T(n/a)+T(n/b)+nk, a>1,b>1,k&#8805;1.

Лабораторная работа 2. Рекуррентные уравнения.
 Задание 1. Решить следующие рекуррентные уравнения:
 1) T( n) =4T(2n/3) + 1, T(1) = 3
 T( n) = T(n-1) + lg n, T(1) = 4
 T( n) = T(n/3) + T(3n/5) + n
 2) T( n) = T(n-1) + n2, T(1) = 1
 T( n) = 3T(3n/4) + n, T(1) = 1
 T( n) = T(n/6) + T(3n/4) + n2
 
 Задание 2. Определите верхнюю и нижнюю асимптотические границы функции T( n) для каждого из перечисленных ниже рекуррентных соотношений. Считаем, что T( n) - константа при достаточно малых n. Обоснуйте свой ответ.
 1) T( n) = 2T(n/2) + n3 
 T( n) = 7T(2n/5)+n2 
 T( n) = 2T(n/4) +n1/2
 
 2) T( n) = T(9n/10) + n 
 T( n) = 6T(n/2) + n2 
 T( n) = 16T(n/4) + n2
 Задание 3*. Решить следующее рекуррентное уравнение: 
 T( n)=T(n/a)+T(n/b)+nk, a&gt;1,b&gt;1,k≥1.

Александр TimmyTayn

Помощь с лабораторной работой по Алгоритмам и структурам данных