Блог

Главная - Вопросы по программированию - Найдите рекуррентное соотношение и оцените сложность

Найдите рекуррентное соотношение и оцените сложность

#algorithm #recursion #time-complexity

Вопрос:

У меня есть 2 псевдокода, и мне нужно знать, как писать рекуррентные отношения кода и как оценивать сложность. Первый из них находится ниже.

 F(n)
if n=0 or n=1 then
   s←n
else
   a←F((n   1) / 2)
   b←F((n   1) / 2 - 1)
if(n mod 2 == 0) then
   s←a * (a   2 * b)
else
   s←a * a   b * b

Второй находится ниже.

 P(x,n)
if n==0 then
   return 1
else
   partial = P(x,n//2)
   result = partial * partial
   if n % 2 == 1 then
      result *= x
return result

Если кто-нибудь сможет это сделать и рассказать о решении шаг за шагом, я был бы очень признателен. Заранее спасибо.

Комментарии:

1. В обоих случаях вам просто нужно выяснить, сколько существует рекурсивных вызовов. Самое простое-это P(x,n) . Сколько существует рекурсивных вызовов? Мы продолжаем n заменять n//2 до n тех пор, пока не будет 0. Сколько раз требуется, чтобы перейти от n 1 к 2, многократно разделив на 2? Ответ таков log_2(n) . Таким образом, количество рекурсивных вызовов P(x,n) равно log_2(n), а сложность равна O(log(n)).

2. Потому F(n) что это немного сложнее. Рекурсивные вызовы также делятся n на 2, но на каждом шаге есть два рекурсивных вызова. Если вы нарисуете диаграмму, вы поймете, что рекурсивные вызовы образуют двоичное дерево. По тому же аргументу , что и для P(x,n) , высота двоичного дерева равна log_2(n). Итак, вопрос в том, сколько узлов в двоичном дереве заданной высоты? Ответ примерно 2**h таков: где h — высота. Таким образом,количество рекурсивных вызовов из F(x, n) составляет около 2**log_2(n), что составляет около n. Таким образом,сложность F(x, n) равна O(n).

3. Хорошо, я понял сложность решения. Это выглядит как нерекурсивная функция. Т. е. для(int i=0i Таким образом, сложность заключается в логне.

4. Итак, можем ли мы написать рекуррентное уравнение? Например, T(n)=…. ?

5. Да на оба ваших комментария.

Ответ №1:

Первый:

 F(n)                  ----------------------T(n)
if n=0 or n=1 then    --------------  1
   s←n                --------------  1
else
   a←F((n   1) / 2)    --------------T(n/2)
   b←F((n   1) / 2 - 1) -------------T(n/2)
if(n mod 2 == 0) then  --------------  1
   s←a * (a   2 * b)   --------------  1
else
   s←a * a   b * b     --------------  1

Что означает,

 T(n) = T(n/2)  T(n/2)   1   1  1   1 

 T(n) = 2*T(n/2)   C  

 using master theorem

 T(n) = O(n)

Второй :

 P(x,n)                  -----------------------------T(n)
if n==0 then                   --------------  1
   return 1                    --------------  1
else
   partial = P(x,n/2) ----------------------T(n/2)
   result = partial * partial  --------------  1
   if n % 2 == 1 then          --------------  1
      result *= x              --------------  1
return result                  --------------  1

что означает,

 T(n) = T(n/2)   C

using master theorem

T(n) = O(log_2 n)     [log_2 --> log base 2]

Примечание : 1 означает постоянное время, C можно рассматривать как 1, не то, чтобы оно вносило какие-либо изменения при решении, также мы могли бы использовать рекурсивное дерево вместо основной теоремы. Просто эта главная теорема была проще.

Метки: