主方法(Master Method)是一種用於分析分治策略算法時間複雜度的有效工具。它基於遞歸分解問題的規模,並分析解決子問題和合併結果所需的時間。主方法的形式通常表示為:
T[n] = aT[n/b] + f(n)
其中:
T[n] 表示規模為 n 的問題的解時間。
a 表示遞歸調用的次數,即生成的子問題數,且 a >= 1。
b 表示每次遞歸問題規模減少的比例,且 b > 1。
f(n) 表示分解問題和合併結果所需的時間。
主方法提供了三種情況來分析時間複雜度:
當 d < log(b) a 时,时间复杂度为 O(n^(log(b) a))。
當 d = log(b) a 時,時間複雜度為 O((n^d) * log(n))。
當 d > log(b) a 時,時間複雜度為 O(n^d)。
其中,d 是問題規模減少的指數,即 n/b 的指數。這個指數通常與問題規模減少的方式有關。例如,如果問題是按平方(即 n^2)減少,則 d = 2。
主方法通過這些情況提供了對分治算法時間複雜度的直觀理解,幫助開發者快速評估算法的效率。