标签：#演算法分析

主定理

在演算法分析中，主定理（）提供了用渐近符号（大O符号）表示许多由分治法得到的递推关系式的方法。这种方法最初由喬恩·本特利、和在1980年提出，在那里被描述为解决这种递推的“天下無敵法”（Master method）。此方法经由经典演算法教科书、、羅納德·李維斯特和的《算法导论》推广而为人熟知。 不过，并非所有递推关系式都可应用支配理论。该定理的推广形式包括。 支配理论 假设有递归关系式 :T(n) = a \; T\!\left(\fr…