递归和master公式

递归和master公式

1. 去画调用图是非常重要的，有利于分析递归
2. 从实际上理解递归:递归不是玄学，底层是利用系统来实现的
3. 任何递归函数都一定可以改成非递归，不用系统帮你压栈(系统栈空间,暂时保存，优先弹出栈顶)，自己压栈呗(内存空间)
4. 递归改成非递归的必要性:
   • 工程上几乎一定要改，除非确定数据量再大递归也一定不深，归并排序、快速排序、线段树、很多的平衡树等（系统栈和内存是两个独立空间，内存栈开销更小）
   • 算法笔试或者比赛中(能通过就不改)
5. master公式
   • 所有子问题规模相同的递归才能用master公式，T(n)=a*T(n/b)+0(n^c)，a、b、c都是常数
   • 如果log(b,a)<C，复杂度为:0(n^c)
   • 如果log(b,a)>c，复杂度为:0(n^log(b,a))
   • 如果log(b,a)==c，复杂度为:0(n^c*1ogn)6)一个补充
6. T(n)= 2T(n/2)+ 0(nlogn)，时间复杂度是0(n*((logn)的平方))，证明过程比较复杂，记住即可

    public static int maxValue(int [] arr){
        return f(arr,0,arr.length - 1);
    }

    //master:T(n)=2*T(n/2)+0(1)
    public static int f(int[] arr , int l, int r){
        if(l==r){
            return arr[l];
        }
        int m = (l+r)/2;
        int lmax = f(arr,0,m);
        int rmax = f(arr,m+1,r);
        return Math.max(lmax,rmax);
    }