对数器

这是一种算法验证机制

选择一种需要验证的方法A，和另一种可能速度有点慢但是已经验证好的方法B

通过随机样本产生器从小到大产生随机样本，来进行实际测试

例如排序我们就可以拿系统的排序算法当成方法B和自己编写的排序算法方法A通过对数器方式进行验证，具体代码可以参考下面图片：

剖析递归行为与递归的时间复杂度计算

这里主要说一下什么是递归，以求数组最大值的算法来举例

同时学习如何基于master公式来进行符合该公司的递归算法时间复杂度计算

示例：求数组最大值

常规该问题可以通过遍历-比较-记录和更新最大值下标来通过O(N)时间解决。

但是这里我们希望采用递归方式，采用递归就要搞清楚最底层如何解决

这里我们通过递归获取leftMax和rightMax并比较大小的方式来获取最终的最大值，对于原数组，首先求出mid将数组一分为二，并计算left侧数组最大值和right侧数组最大值，求数组最大值的process可以无限递归下去：

public static int getMax(int[] arr){

    return process(arr, 0, arr.length-1);

}



public static int process(int[] arr,int L, int R){

    // 求arr L-R区间最大值

    if(L == R){

        return arr[L];

    }

    // 这种求中点算法是为了避免相加值溢出

    int mid = L + ((R-L) >> 1); 

    // 递归需要传入一个不变的原始数据 - arr

    int leftMax = process(arr, L, mid);

    int rightMax = process(arr, mid+1, R);

    return Math.max(leftMax,rightMax);

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

求中点好的算法：

递归过程（利用函数栈压栈和出栈玩了一个后续遍历）：

master公式

接着我们用上面示例来描述一些什么是master公式

T(N)代表母问题，就是根问题

a*T(N/b)代表我调用了N/b规模的子问题 a 次

最后的O(N^d)代表除去子问题调用之外的时间复杂度

以上这种递归可以用master公式求解复杂度

刚刚的问题我们只看一层试一试：

子问题问题是不是等量？可以看到调用自己时候都是一半切开，所以是N/2规模，另一半也是N/2规模，子问题都是等量。

而且调用left和right了两次

剩余操作就是求中点和比大小 -> O(1)的复杂度

所以我们之前的函数满足master公式

另外如果我们对数组左侧3/2 调了递归，右侧2/3调了递归（只不过有1/3重叠），那么也符合master公式：

上述算法，a=2，b=2，d=0 那么log2^2 = 1 > 0 所有最终复杂度O(N)!