算法学习笔记（四）递归中时间复杂度的估算

如果递归行为符合T(N) = aT(N/b) + O(N^d)，就可以直接利用master公式来得到时间复杂度。a代表子过程调用的次数，N/b是子问题规模，除了子过程之外的部分的时间复杂度需要满足O(N^d)。其中要注意的是，想要使用master公式，子过程的规模要相同，都是N/b。

Master公式：

（1）log_ba > d —> O(N^(log_ba))

（2）log_ba < d —> O(N^d)

（3）log_ba = d —> O(N^d * logN)

“获得一个数组中的最大值”可以直接通过遍历来完成，但为了解释上述知识点，用递归的方式来实现：先找到中点位置，分别求出并比较左右两边数的最大值，递归停止的条件是左右下标相同，也就是同一个位置。具体代码如下：

Java

public static int getMax(int[] arr) {
        return process(arr, 0, arr.length-1);
    }
    public static int process(int[] arr, int left, int right) {
        // the base case
        if(left == right) {
            return arr[left];
        }
        int mid = left + ((right - left) >> 1);
        int leftMax = process(arr, left, mid);
        int rightMax = process(arr, mid+1, right);
        return Math.max(leftMax, rightMax);
    }

JavaScript

function getMax(arr){
      return process(arr,0,arr.length-1);
    }

    function process(arr, left, right){
      if(left == right) {
          return arr[left];
      }
      var mid = left + ((right - left) >> 1);
      var leftMax = process(arr, left, mid);
      var rightMax = process(arr, mid+1, right);
      return Math.max(leftMax, rightMax);
    }

根据上面的代码，可以看出子过程的规模是N/2,调用子过程的次数是2次，除了子过程之外的部分时间复杂度是O(1)。整体的表达式可以写作：T(N) = 2T(N/2) + O(1)，符合master公式的要求，因此可以直接代入使用。a=2, b=2, d=0，那么log₂2 = 1 > 0，时间复杂度为O(N^log₂2) = O(N)。这和直接遍历找出最大值的时间复杂度相同。

如果在代码中加入一个(和功能无关的）for循环，那么除了子过程之外的部分时间复杂度为O(N)，T(N) = 2T(N/2) + O(N)。示例如下：

public static int getMax(int[] arr) {
        return process(arr, 0, arr.length-1);
    }
    public static int process(int[] arr, int left, int right) {
        if(left == right) {
            return arr[left];
        }
        
        // 假如在代码中加入下面的语句, T(N) = 2T(N/2) + O(N)
        for(int i=left; i<=right; i++) {
            System.out.println(arr[i]);
        }
        
        int mid = left + ((right - left) >> 1);
        int leftMax = process(arr, left, mid);
        int rightMax = process(arr, mid+1, right);
        return Math.max(leftMax, rightMax);
    }