勵志

勵志人生知識庫

主定理

主定理(Master Theorem)是算法分析領域中的一個定理,主要用於分析遞歸算法的時間複雜度。它提供了用漸近符號(大O符號)表示許多由分治法得到的遞推關係式的方法。這種方法最初由Jon BentleyDorothea HakenJames B. Saxe在1980年提出,被描述為解決這種遞推的「天下無敵法」(master method)。後來,該方法經由經典算法教科書《算法導論》的推廣而廣為人知。但需要注意的是,並非所有遞推關係式都可套用主定理,該定理的推廣形式包括Akra-Bazzi定理等。