主定理

在演算法分析中，主定理（英語：master theorem）提供了用渐近符号（大O符号）表示许多由分治法得到的递推关系式的方法。这种方法最初由，和在1980年提出，在那里被描述为解决这种递推的“天下無敵法”(master method)。此方法经由经典演算法教科书，，和Stein的《算法导论》 (introduction to algorithm) 推广而为人熟知。 不过，并非所有递推关系式都可应用支配理论。该定理的推广形式包括。