在演算法分析 中,主定理 (英語:Master theorem )提供了用漸近符號(大O符號 )表示許多由分治法 得到的遞推關係式 的方法。這種方法最初由喬恩·本特利 、多蘿西·布洛斯坦 和詹姆斯·B·薩克斯 在1980年提出,在那裡被描述為解決這種遞推的「天下無敵法」(Master method)。此方法經由經典演算法教科書托馬斯·H·科爾曼 、查爾斯·E·雷瑟爾森 、羅納德·李維斯特 和克利福德·史坦 的《演算法導論 》推廣而為人熟知。
不過,並非所有遞推關係式都可應用支配理論。該定理的推廣形式包括阿克拉-巴茲方法 。
支配理論
假設有遞迴關係式
T
(
n
)
=
a
T
(
n
b
)
+
f
(
n
)
{\displaystyle T(n)=a\;T\!\left({\frac {n}{b}}\right)+f(n)}
,其中
a
≥
1
,
b
>
1
{\displaystyle a\geq 1{\mbox{, }}b>1}
其中,
n
{\displaystyle n}
為問題規模,
a
{\displaystyle a}
為遞迴的子問題數量,
n
b
{\displaystyle {\frac {n}{b}}}
為每個子問題的規模(假設每個子問題的規模基本一樣),
f
(
n
)
{\displaystyle f(n)}
為遞迴以外進行的計算工作。
情形一
如果存在常數
ϵ
>
0
{\displaystyle \epsilon >0}
,有
f
(
n
)
=
O
(
n
log
b
(
a
)
−
ϵ
)
{\displaystyle f(n)=O\left(n^{\log _{b}(a)-\epsilon }\right)}
(可不嚴謹的視作多項式地小於)
則
T
(
n
)
=
Θ
(
n
log
b
a
)
{\displaystyle T(n)=\Theta \left(n^{\log _{b}a}\right)}
情形二
如果存在常數
ϵ
≥
0
{\displaystyle \epsilon \geq 0}
,有
f
(
n
)
=
Θ
(
n
log
b
a
log
ϵ
n
)
{\displaystyle f(n)=\Theta \left(n^{\log _{b}a}\log ^{\epsilon }n\right)}
則
T
(
n
)
=
Θ
(
n
log
b
a
log
ϵ
+
1
n
)
{\displaystyle T(n)=\Theta \left(n^{\log _{b}a}\log ^{\epsilon +1}n\right)}
情形三
如果存在常數
ϵ
>
0
{\displaystyle \epsilon >0}
,有
f
(
n
)
=
Ω
(
n
log
b
(
a
)
+
ϵ
)
{\displaystyle f(n)=\Omega \left(n^{\log _{b}(a)+\epsilon }\right)}
(多項式地大於)
同時存在常數
c
<
1
{\displaystyle c<1}
以及充分大的
n
{\displaystyle n}
,滿足
a
f
(
n
b
)
≤
c
f
(
n
)
{\displaystyle af\left({\frac {n}{b}}\right)\leq cf(n)}
則
T
(
n
)
=
Θ
(
f
(
n
)
)
{\displaystyle T\left(n\right)=\Theta \left(f\left(n\right)\right)}
常用演算法中的應用
演算法
遞迴關係式
運算時間
備註
二分搜尋演算法
T
(
n
)
=
T
(
n
2
)
+
Θ
(
1
)
{\displaystyle T(n)=T\left({\frac {n}{2}}\right)+\Theta (1)}
Θ
(
log
n
)
{\displaystyle \Theta (\log n)}
情形二(
ϵ
=
0
{\displaystyle \epsilon =0}
)
二元樹 遍歷
T
(
n
)
=
2
T
(
n
2
)
+
Θ
(
1
)
{\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+\Theta (1)}
Θ
(
n
)
{\displaystyle \Theta (n)}
情形一
最佳排序矩陣搜尋(已排好序的二維矩陣)
T
(
n
)
=
2
T
(
n
2
)
+
O
(
log
n
)
{\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+O(\log n)}
Θ
(
n
)
{\displaystyle \Theta (n)}
合併排序
T
(
n
)
=
2
T
(
n
2
)
+
Θ
(
n
)
{\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+\Theta (n)}
Θ
(
n
log
n
)
{\displaystyle \Theta (n\log n)}
情形二(
ϵ
=
0
{\displaystyle \epsilon =0}
)
參考文獻
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms , Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7 . Sections 4.3 (The master method) and 4.4 (Proof of the master theorem), pp. 73–90.
Michael T. Goodrich and Roberto Tamassia. Algorithm Design: Foundation, Analysis, and Internet Examples . Wiley, 2002. ISBN 0-471-38365-1 . The master theorem (including the version of Case 2 included here, which is stronger than the one from CLRS) is on pp. 268–270.