前言
1、递归算法性能分析公式
1.1 时间复杂度计算公式
递归算法的时间复杂度 = 递归的次数 * 每次递归的时间复杂度。
1.2 空间复杂度计算公式
递归算法的空间复杂度 = 递归的深度 * 每次递归的空间复杂度。
1.3 例子
计算整数x的n次方
1.3.1 暴力算法
int function(int x, int n) {
int ans = 1; for(int i = 0; i < n; i++) {
ans = ans * x; } return ans; } 时间复杂度为O(n)，空间复杂度为O(1)。
1.3.2 递归算法
int recursion(int x, int n) {
if (x == 0) return 0; if(n == 0) return 1;// 整数（零除外）的0次方为1 if(n == 1) return x;// 退出递归条件 return recursion(x, n - 1) * x; } 1.3.3 优化递归算法
为了降低时间复杂度，那么就需要O(log n)复杂度，假设每次递归时间复杂度为常熟O（1），那么，递归次数就需要为m = log n次。因为2^m = n,那么每次递归都可以减半，这样就可以重复利用这次递归结果，大大降低时间复杂度。
int recursion2(int x, int n) {
if(x == 0) return 0; if(n == 0) return 1;// 整数（零除外）的0次方为1 if(n == 1) return x;// 退出递归条件 int temp = recursion1(x, n / 2); if(n % 2 == 1) {
return temp * temp * x;// n为奇数时 } return temp * temp;// n为偶数时 } 总结
在使用递归时，需要注意，是否存在多余计算，如何减少重复计算部分，就可对此进行优化处理。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/214691.html原文链接：https://javaforall.net
