[数据结构与算法]递归的简单应用以及master公式

1. 简单的认识递归法

求数组中的最大值

#include<iostream>
#include<vector>
using namespace std;

int get_max(vector<int>& Arr,int start,int end)
{
	if (start == end)
		return Arr[start];
	int mid =  (start + end) >> 1;
	return max(get_max(Arr, start, mid), get_max(Arr, mid + 1, end));
}

int main()
{
	vector<int> Arr{ 1,2,3,7,5,3,9,3,5 };
	int res = get_max(Arr, 0, Arr.size() - 1);
	cout << res << endl;
	return 0;
}

master公式

对于符合子问题规模等规模的递归问题，可以使用master公式快速得到时间复杂度
master公式为：
T(N) = a$\times$T($\frac{N}{b}$) + O(N^d)
举例1:求一个数组的做大值，寻找策略为寻找左右两半的最大值，然后比较得到全部数组的最大值。那么a=2,b=2,d=0,因为决策过程只是比较left是否等于right，然后比较左右两边的最大值，所以决策过程的时间复杂度为O(1);这个寻找策略就符合master公式
举例2: 寻找策略如果是寻找左边1/3数组的最大值，右边2/3的最大值，那么就不符合master公式，因为子问题的规模不等规模

master公式求时间复杂度的方式

1. log(b,a)<d    时间复杂度O(N^d)
2. lob(b,a)>d    时间复杂度O(N^log(b,a))
3. lob(b,a)=d    时间复杂度O(N^d*log(N))

阅读世界，共赴山海

423全民读书节，邀你共读