主定理"Master Theorem"
- 一、主定理(Master Theorem)
- 二、應用舉例
在分析算法的時候，我們經常需要分析遞歸算法的時間複雜度。
一、主定理(Master Theorem)
主定理适用于求解如下遞歸式算法的時間複雜度：
其中：
- n 是問題規模大小；
- a 是原問題的子問題個數；
- n/b 是每個子問題的大小，這裡假設每個子問題有相同的規模大小；
- f(n) 是将原問題分解成子問題和将子問題的解合并成原問題的解的時間。
對上面的式子進行分析，得到三種情況：
二、應用舉例