前言

根据代码随想录博主整理的
主要是为了记录递归算法如何分析其性能，并如何根据其性能来优化递归算法。

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;
}

时间复杂度 = 递归的次数 * 每次递归的时间复杂度 = O((n – 1) * 1) = O(n)；
空间复杂度 = 递归深度 * 每次递归的空间复杂度 = O((n – 1) * 1) = O(n);

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为偶数时
}

时间复杂度 = 递归的次数 * 每次递归的时间复杂度 = O((log n) * 1) = O(log n)；
空间复杂度 = 递归深度 * 每次递归的空间复杂度 = O((n – 1) * 1) = O(n);

总结

在使用递归时，需要注意，是否存在多余计算，如何减少重复计算部分，就可对此进行优化处理。

今天的文章递归算法时间复杂度和空间复杂度分析与举例分享到此就结束了，感谢您的阅读。