查找递归关系并评估复杂性

Question

我有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

如果有人能做到这一点并一步步告诉解决方案，我将不胜感激。提前致谢。

Answer 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，不是说求解的时候会改变，也可以用递归树代替主定理。只是那个主定理比较简单。

查找递归关系并评估复杂性

Find recurrence relation and evaluate the complexity

algorithm

recursion

time-complexity