1.1.7 master公式的使用

code 递归例子 – 返回最大数据

# 递归行为， 返回[L, R]的最大值
# 递归：base case； 遍历；返回值
from test1 import *def getMax(arr):return process(arr, 0, len(arr)-1)def process(arr, L, R):if (L == R):return arr[L]    # base casemid = L + ((R - L) >> 1)   # 中点， 避免溢出  L + (R - L) // 2; 位运算加速leftMax = process(arr, L, mid)rightMax = process(arr, mid + 1, R)return max(leftMax, rightMax)arr = generateRandomArray(maxSize=100, maxValue=100)
printArray(arr)
max1 = getMax(arr)

例子

arr = [3, 2, 5, 6, 7, 4]
ind = [0, 1, 2, 3, 4, 5]
调用过程： 递归的调用。系统栈=压栈p(0, 5)p(0, 2)                 p(3,5)    p(0,1)      p(2,2)       p(3,4)      p(5,5)
p(0,0) p(1,1)           p(3,3)  p(4,4)    

master公式的使用

剖析递归行为和递归行为时间复杂度的估算
用递归方法找一个数组中的最大值，系统上到底是怎么做的？
master公式的使用
$$T(N)=a\ast T(N/b)+O(N^d)$$

1. log(b,a) > d -> 复杂度为O(N^log(b,a))
2. log(b,a) = d -> 复杂度为O(N^d * logN)
3. log(b,a) < d -> 复杂度为O(N^d)

$T(N)$: 母问题的数据量是$n$级别；
$T(N/b)$: 子问题的规模都是等分为$b$份；每份是$N/b$的规模；
$a$: 子问题被调用了几次；
$O(N^d)$: 除去子问题的调用外，剩余的操作的时间复杂度。

T(N) = a * T(N/b) + O(N^d)
母       次数  子问题    额外

满足上面几点就可以使用master公式。

getMax(arr)函数的调用：
$$T(N)=2\ast T(N/b)+O(1)$$