递归算法时间复杂度分析（master公式使用）
欢迎关注本人公众号：Bean冷的心，内容包含计算机网络、数据结构与算法、科技资讯和知识扫盲，期待结实各位大佬和对计算机感兴趣的小伙伴~
看了左神的求递归算法时间复杂度分析受益颇多，在这里写一下收获：
master公式的使用
T(N) = a*T(N/b) + O(N^d)
1) log(b,a) > d ->复杂度为O（N^log(b,a)）
2) log(b,a) = d ->复杂度为O（N^d*logN）
3) log(b,a) < d ->复杂度为O（N^d）
什么意思呢？
a：迭代子算法有几个
b：每个子算法负责多少数据
d：除去子过程剩下的时间复杂度的指数
看一个简单的递归程序：
package com.bean.com.bean.sample;
public class EasyRecurrence {
//求数组中最大的元素
public static int getMax(int[] arr, int left, int right) {
if (left == right) {
return arr[left];
}
int mid = (left + right) / 2;
int leftMax = getMax(arr, left, mid);
int rightMax = getMax(arr, mid+1, right);
return Math.max(leftMax, rightMax);
}
public static void main(String[] args) {
int[] arr = {4,2,1,66,48};
System.out.println(getMax(arr,0,arr.length-1));
}
}
由于递归是将原本复杂的方法划分为很多小问题，所以这个小栗子程序的abd分别是什么呢？
首先被求最大值这个问题被分成了两部分，左半部分只求左半部分的最大值，右半部分只求右半部分的最大值，所以a = 2；每个子过程负责多大面积呢？假设总共N个数据的话，left只负责N/2，right也只负责N/2的数据，所以b = 2；除去迭代算法，时间复杂度就是O（1）,也就是N的0次方，所以d = 0；
所以
T(N) = 2*T(n/2) + O(n^0)
套master公式：log以b为底a的对数等于log2，也就是1,1是大于d=0的，所以执行第一个，时间复杂度为：O（N^log(2,2)）= O（N）
很简单吧？
欢迎关注本人公众号：Bean冷的心，内容包含计算机网络、数据结构与算法、科技资讯和知识扫盲，期待结实各位大佬和对计算机感兴趣的小伙伴~
版权声明：本文为taobean原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。