我将如何为这样的算法建立递归关系?
How would I go about making a recurrence relation for an algorithm like this?
我需要找到该算法执行的乘法次数的递归关系,该算法找到 base^n,但由于底部的 IF,我真的不知道该怎么做。
public int reduceAndConquer(int base, int n){
if(n == 1) return base;
if(n == 2) return base*base;
else{
int total = reduceAndConquer(base, n/2);
if(n%2 == 0) return total*total;
return total*total*base;
}
}
由于它是 1 次或 2 次乘法,具体取决于它是偶数还是奇数,我不确定如何将其转化为关系。任何输入都会有所帮助。
我认为你可以在递归关系中做 even/odd 个分支:
T(n) = T(n/2)+1 for n even
T(n) = T(floor(n/2))+2 for n odd
或另一种表达方式:
T(2k) = T(k)+1
T(2k+1) = T(k)+2
或者如果你真的想要一个公式:
T(n) = T(floor(n/2)) + 1 + n%2
对于 n-(2*floor(n/2))
,n%2 当然是 shorthand
我需要找到该算法执行的乘法次数的递归关系,该算法找到 base^n,但由于底部的 IF,我真的不知道该怎么做。
public int reduceAndConquer(int base, int n){
if(n == 1) return base;
if(n == 2) return base*base;
else{
int total = reduceAndConquer(base, n/2);
if(n%2 == 0) return total*total;
return total*total*base;
}
}
由于它是 1 次或 2 次乘法,具体取决于它是偶数还是奇数,我不确定如何将其转化为关系。任何输入都会有所帮助。
我认为你可以在递归关系中做 even/odd 个分支:
T(n) = T(n/2)+1 for n even
T(n) = T(floor(n/2))+2 for n odd
或另一种表达方式:
T(2k) = T(k)+1
T(2k+1) = T(k)+2
或者如果你真的想要一个公式:
T(n) = T(floor(n/2)) + 1 + n%2
对于 n-(2*floor(n/2))
,n%2 当然是 shorthand