# EE資料結構#3 - Master Theorem

分析recursion以及dynamic programming的複雜度的時候
可以用到的定理

把本來size=n的問題分成a個size為n/b的問題
分解的時候需要時間f(n)
(ab不一定要相等)

總需要的時間就是a倍f(n/b) + 分解的f(n)


原理大概是將遞迴往下拆，會發現是等比級數，因為公比的不同而有不同結果

若d很小，f(n)微不足道可忽略，假設T(n)為n^p
則T(n)=a(n/b)^p=n^p，可解得p=log(b)a，即定理內容

若d很大，則以f(n)為主，即n^d

* 例：T(n)=T(1/2)+1　Binary Search
a=1 b=2 f(n)=1 d=0，中間的case
所以T(n)=log n


case 1對應Theorem 1的第一種情況（theta跟big O差不多意思）
case 2對應Theorem 1的第二種+下方情況
case 3對應Theorem 1的第三種情況
case 4用在f(n)非多項式，但至少是n^c的話，此時由後者決定

###### tags: `python` `資料結構`