设求解某问题的递归算法如下: F(int n){ if n=1 {Move(1) }else{ F(n－1); Move(n); F(n－1); } }

Question

设求解某问题的递归算法如下：

F(int n){

if n=1 {

Move(1)

}else{

F(n-1)；

Move(n)；

F(n-1)；

}

}

求解该算法的计算时间时，仅考虑算法Move所做的计算为主要计算，且Move为常数级算法。则算法F的计算时间T(n)的递推关系式为(9)；设算法Move的计算时间为k，当 n=4时，算法F的计算时间为(10)。

A．T(n)=T(n-1)+1

B．T(n)=2T(n-1)

C．T(n)=2T(n-1)+1

D．T(n)=2T(n+1)+1

Answer 1

正确答案：C