主定理 发表于 2022-03-20 分类于 编程 文章字数：79,阅读全文大约需要1分钟 主定理最早出现在《算法导论》中，提供了分治方法带来的递归表达式的渐进复杂度分析。规模为n的问题通过分治，得到a个规模为n/b的问题，每次递归带来的额外计算为c(n^d) 计算T(n) <= aT(n/b) + c(n^d) T(n) = O(n^d log(n)) , if a = b^d T(n) = O(n^d) , if a < b^d T(n) = O(n^logb(a)) , if a > b^d