数据结构之递归时间复杂度、空间复杂度

• 递归空间复杂度
• • 1.遍历求x的n次方时间复杂度O(n)
  • 2.递归求x的n次方时间复杂度O(n)
  • 3.递归求x的n次方时间复杂度O(n)
  • 4.递归求x的n次方时间复杂度logn
  • 5.递归求斐波那契数列时间复杂度O(2^n)、空间复杂度O(1)

空间复杂度是logn的情况确实有些特殊，其实是在递归的时候，会出现空间复杂度为logn的情况

面试题：求x的n次方
时间复杂度为O(n)

func function1(x, n int) int {
	result := 1 // 注意 任何数的0次方等于1
	for i := 0; i < n; i++ {
		result = result * x
	}
	return result
}

递归算法的时间复杂度本质上是要看: 递归的次数 * 每次递归中的操作次数。
那再来看代码，这里递归了几次呢？
递归了n次时间复杂度是O(n)，每次进行了一个乘法操作，乘法操作的时间复杂度一个常数项O(1)，所以这份代码的时间复杂度是 n × 1 = O(n)。

func function2(x, n int) int {
	if n == 0 {
		return 1 // return 1 同样是因为0次方是等于1的
	}
	return function2(x, n-1) * x

}

以下递归的算法依然还是O(n)

func function3(x, n int) int {
	if n == 0 {
		return 1
	}
	if n%2 == 1 {
		return function3(x, n/2) * function3(x, n/2) * x
	}
	return function3(x, n/2) * function3(x, n/2)
}

我们来分析一下，首先看递归了多少次呢，可以把递归抽象出一棵满二叉树。写的这个算法，可以用一棵满二叉树来表示（为了方便表示，选择n为偶数16），如图：
当前这棵二叉树就是求x的n次方，n为16的情况，n为16的时候进行了多少次乘法运算呢？
这棵树上每一个节点就代表着一次递归并进行了一次相乘操作，所以进行了多少次递归的话，就是看这棵树上有多少个节点
熟悉二叉树话应该知道如何求满二叉树节点数量，这棵满二叉树的节点数量就是2^4++2^3 + 2^2 + 2^1 + 2^0 = 31，可以发现：这其实是等比数列的求和公式，这个结论在二叉树相关的面试题里也经常出现

这么如果是求x的n次方，这个递归树有多少个节点呢，经验证是2n-1
时间复杂度忽略掉常数项-1与常数项系数2之后，这个递归算法的时间复杂度依然是O(n)

func function3(x, n int) int {
	if n == 0 {
		return 1
	}
	if n%2 == 1 {
		return function3(x, n/2) * function3(x, n/2) * x
	}
	return function3(x, n/2) * function3(x, n/2)
}
func main() {
	//也可以算奇数
	fmt.Println(function3(2, 5))//32
}

刚刚给出的那份递归算法的代码，是不是有哪里比较冗余呢，其实有重复计算的部分。
再来看一下现在这份代码时间复杂度是多少呢？
依然还是递归了多少次，可以看到这里仅仅有一个递归调用，且每次都是n/2 ，所以这里我们一共调用了log以2为底n的对数次。
每次递归了做都是一次乘法操作，这也是一个常数项的操作，那么这个递归算法的时间复杂度才是真正的O(log n)。

func function4(x, n int) int {
	if n == 0 {
		return 1
	}
	t := function4(x, n/2) // 这里相对于function3，是把这个递归操作抽取出来
	if n%2 == 1 {
		return t * t * x
	}
	return t * t
}

以下递归求斐波那契数列时间复杂度O(2^n)、空间复杂度O(1)

func fibonacci(i int) int {
	if i <= 0 {
		return 0
	}
	if i == 1 {
		return 1
	}
	return fibonacci(i-1) + fibonacci(i-2)
}
func main() {
	fmt.Println(fibonacci(3)) //2
}

来看看这个求斐波那契的递归算法的时间复杂度是多少呢？
在讲解递归时间复杂度的时候，我们提到了递归算法的时间复杂度本质上是要看: 递归的次数 * 每次递归的时间复杂度。
可以看出上面的代码每次递归都是O(1)的操作。再来看递归了多少次，这里将i为5作为输入的递归过程 抽象成一棵递归树，如图：
从图中，可以看出f(5)是由f(4)和f(3)相加而来，那么f(4)是由f(3)和f(2)相加而来 以此类推。
在这棵二叉树中每一个节点都是一次递归，那么这棵树有多少个节点呢？
我们之前也有说到，一棵深度（按根节点深度为1）为k的二叉树最多可以有 2^k - 1 个节点。
所以该递归算法的时间复杂度为O(2^n)，这个复杂度是非常大的，随着n的增大，耗时是指
数上升的。
其实罪魁祸首就是这里的两次递归，导致了时间复杂度以指数上升

说完了这段递归代码的时间复杂度，再看看如何求其空间复杂度呢，这里给大家提供一个公式：递归算法的空间复杂度 = 每次递归的空间复杂度 * 递归深度
为什么要求递归的深度呢？
因为每次递归所需的空间都被压到调用栈里（这是内存管理里面的数据结构，和算法里的栈原理是一样的），一次递归结束，这个栈就是就是把本次递归的数据弹出去。所以这个栈最大的长度就是递归的深度。
此时可以分析这段递归的空间复杂度，从代码中可以看出每次递归所需要的空间大小都是一样的，所以每次递归中需要的空间是一个常量，并不会随着n的变化而变化，每次递归的空间复杂度就是O(1)。
在看递归的深度是多少呢？如图所示：
递归第n个斐波那契数的话，递归调用栈的深度就是n。
那么每次递归的空间复杂度是O(1)， 调用栈深度为n，所以这段递归代码的空间复杂度就是O(n)。