代码随想录学习之---递归算法复杂度分析

递归算法复杂度分析

问题：求x的n次方

O(n)的解法：

int function1(int x, int n) {
	int t = 1; //x的0次方是1
	for (int i=0; i < n; i++)
		t = t * x;
	return t;
}
           

上面方法的思路很简单，就是每次多乘一个x，一共n个x相乘所以一个for循环搞定，时间复杂度也不难看出来是O(n)。但是，有没有其他的办法呢？

递归算法

递归算法可以分为三个步骤：①定义函数②找到等价关系式③确定终止条件

----以斐波那契数列为例—

定义函数：fib(n)

找到等价关系式：fib(n-1)+fib(n-2)

终止条件：if (n <= 2) fib(n) = 1

那么最开始的问题也可以想办法用递归的办法想，n个x相乘等价于 (n-1)个x * x 。如此，递归下去当n=0时就是终止条件了嘛，此时结果为0

int function2(int x, int n) {
	if (n == 0)
		return 1;
	return function2(x, n-1) * x;
}
           

首先，需要明确递归算法的时间复杂度是 递归的次数 × 每次递归中的操作数

每次递归中仅有一个相乘的操作，其实他的时间复杂度也是O(n)。举个例子，当n=3时，第一次递归后：n=2;第二次递归后，n=1;第三次递归后，n=0此时返回1.

那么有没有更好的办法呢？分析一下可以发现，n要么是奇数，要么是偶数。如果n是偶数，那么此时可以看成x的n/2次方 × x的n/2次方。如果n是奇数，可以看成是x × x的偶数次方（回到了第一种情况）。

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

那么时间复杂度怎么分析呢？假设n=16,

第一次递归，可以分为2个节点，每个节点有8个x相乘

第二次递归，可以分为4个节点，每个节点有4个x相乘

第三次递归，可以分为8个节点，每个节点有2个x相乘

看成一个满二叉树的话，一共有15个节点，每个节点有一次相乘操作。所以时间复杂度O(n-1)，也就是O(n)。

进一步可以对上面的函数进行优化，function3(x, n/2)被计算了两次，其实计算一次就可以了没必要浪费时间。

int funciton4(int x, int n) {
	if (n == 0)
		return 1;
	int t = funtion4(x, n/2);
	if (n % 2 == 1)
		return t * t * x;
	return t *t;
}
           

这里仅仅有一个递归调用，且每次都是n/2 ，所以这里我们一共调用了log以2为底n的对数次。如果n是奇数，那就有2次相乘，n是偶数那就有1次相乘，最后时间复杂度是O（logn）。

此文章为本人学习笔记，水平有限请多包涵。