java - 我将如何为这样的算法建立递归关系?
问题描述
我需要找到为找到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 次乘法,具体取决于它是偶数还是奇数,我不确定如何将其转化为关系。任何输入都会有所帮助。
解决方案
我认为您可以在递归关系中进行偶数/奇数分支:
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 当然是 n-(2*floor(n/2)) 的简写
推荐阅读
- json - 如何获取包含特定值的 JSON 节点?
- android-constraintlayout - ConstraintLayout 1.1.0 视图不能在同一条边上相互引用?
- .net - 通过 TextFieldParser 类收集行偏移量(以字节为单位)
- react-native - sayem 登录中的“开发者名称”是什么?
- apache-kafka - 代理列表和引导服务器有什么区别?
- python - 比较数据框中的行以更改值
- r - R data.frame 删除因子
- django - Django:隐藏/孤立的 oneToOneField 值
- html - 有 3 个部分(div)向左、中和右浮动
- java - 替换特殊字符之间的数据