设求解某问题的递归算法如下: 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)的递推关系式为(53)：设算法Move的计算时间为k，当n=4时，算法F的计算时间为(54)。

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
解析：本题考查对计算杉1算法进行时间复杂度分析的基本方法。直接递归算法的计算时间可以根据递归调用形式对应写出其递推关系式。按照题目中描述的算法形式，可知算法F的计算时间T(n)的递推关系式为T(n)=2T(n-1)+1，其中两次递归调用F(n-1)用时2T(n-1)，算法Move的计算时间为常数，计为1。将上述递推关系式中常数1用k替换，求解可得T(n)=2^n-1T(1)+，易知　T(1)=k，将n=4代入可得计算时间为15k。