master公式求解时间复杂度
递归求解最大值
int max(const vector<int>& arr,int left,int right){
if(left==right)return arr[left];
int mid=left+(right-left)>>1;
int max1=max(0,mid);
int max2=max(mid+1,arr.size()-1);
return max(max1,max2);
}
应用master公式条件：
子问题必须等规模；
递归的时间复杂度：
T(N)=a*T(N/b)+O(N^d)
N/b：子问题规模
a: 子问题被调用次数
N^d: 其他递归操作复杂度
上面例子中，T(N)=2*T(N/2)+O(1)
结论：
if logb(a)<d ,then T(N)=O(N^d)
if logb(a)>d,then T(N)=O(N^logb(a))
if logb(a)=d,then T(N)=O(N^d*(logN))
版权声明：本文为qq_43536978原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。