渐近符号与主定理求解递归式

发表于 分类于 阅读次数： 本文字数： 468 阅读时长 ≈ 2 分钟

参考《算法导论》的版本

渐近符号

符号 表示 界限 情况 集合表示
渐近上界 最坏复杂度
渐近上界和渐近下界 平均复杂度
渐近下界 最好复杂度

集合表示的条件与格式为：存在正常量（、）和，使得对所有，有

主定理

令 和 是常数， 是一个函数， 是定义在非负整数上的递归式。

规模为的问题分解为 个子问题，每个子问题规模为

其中将 解释为 或 ， 是某个常数且 ，那么 有如下渐近界：

条件 结论 理解
渐近小于
两者等于，乘上对数因子
，且对某个常数 和所有足够大的 ，有 在多项式意义上大于 ，且满足“正则”条件

(书中跟维基里的不一样，书简化了。)

注意三种情况中间有“缝隙”，就不能用主定理求解。

题目

出自算法导论54页

答案 1. 情况1， 2. 情况2， 3. 情况3， 4. 情况2与3的缝隙，不能用主定理求