递归

Master公式

时间复杂度计算公式 :

06. 递归 - 图1%20%3D%20%20aT%20(N%2Fb)%20%2B%20O(N%5Ed)%0A#card=math&code=T%28N%29%20%3D%20%20aT%20%28N%2Fb%29%20%2B%20O%28N%5Ed%29%0A)

06. 递归 - 图2%20%3D%20%E5%AD%90%E9%97%AE%E9%A2%98%E8%B0%83%E7%94%A8%E6%AC%A1%E6%95%B0*T(%E5%AD%90%E9%97%AE%E9%A2%98%E8%A7%84%E6%A8%A1)%20%2B%20%E9%99%A4%E9%80%92%E5%BD%92%E5%A4%96%E5%85%B6%E4%BB%96%E6%89%80%E6%9C%89%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%0A#card=math&code=T%28%E9%97%AE%E9%A2%98%E8%A7%84%E6%A8%A1%29%20%3D%20%E5%AD%90%E9%97%AE%E9%A2%98%E8%B0%83%E7%94%A8%E6%AC%A1%E6%95%B0%2AT%28%E5%AD%90%E9%97%AE%E9%A2%98%E8%A7%84%E6%A8%A1%29%20%2B%20%E9%99%A4%E9%80%92%E5%BD%92%E5%A4%96%E5%85%B6%E4%BB%96%E6%89%80%E6%9C%89%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%0A)

形如上述公式的递归函数(a,b,c 都是常数)的递归函数,可以直接通过Master公式来直接确定时间复杂度

如果时间复杂度满足以上公式 :

  1. loga > d 时间复杂度为 O(N^loga)
  2. loga > d 时间复杂度为 O(N)
  3. loga == d 时间复杂度为 **O(N logN)

举例:

  1. public class GetMax {
  3.     // 求arr中的最大值
  4.     public static int getMax(int[] arr) {
  5.         return process(arr, 0, arr.length - 1);
  6.     }
  8.     // arr[L..R]范围上求最大值 L ... R N
  9.     public static int process(int[] arr, int L, int R) {
  10.         // arr[L..R]范围上只有一个数，直接返回，base case
  11.         if (L == R) {
  12.             return arr[L];
  13.         }
  14.         // L...R 不只一个数
  15.         // mid = (L + R) / 2
  16.         int mid = L + ((R - L) >> 1); // 中点 1
  17.         int leftMax = process(arr, L, mid);
  18.         int rightMax = process(arr, mid + 1, R);
  19.         return Math.max(leftMax, rightMax);
  20.     }
  22. }

06. 递归 - 图3%20%3D%20%202T%20(N%2F2)%20%2B%20O(N%5E0)%0A#card=math&code=%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%20%3A%20T%28N%29%20%3D%20%202T%20%28N%2F2%29%20%2B%20O%28N%5E0%29%0A)

a = 2 , b = 2 , d = 0

时间复杂度为 : loga = log2 = 1 > 0 => O(N)