递归算法时间复杂度和空间复杂度分析与举例

发布时间:2023-03-16 08:00

文章目录

  • 前言
  • 1、递归算法性能分析公式
    • 1.1 时间复杂度计算公式
    • 1.2 空间复杂度计算公式
    • 1.3 例子
    • 1.3.1 暴力算法
    • 1.3.2 递归算法
    • 1.3.3 优化递归算法
    • 总结


前言

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


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

总结

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

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网,如有侵权请联系:561261067@qq.com

桂ICP备16001015号