跳转至

扩展学习：递归式求解时间复杂度的方法——递归树与主定理

代入法不做介绍

想要了解更多推荐专栏：

递归式求解——代入法、递归树与主定理

https://zhuanlan.zhihu.com/p/540889250

https://zhuanlan.zhihu.com/p/541678195

  1. 下列代码的时间复杂度是（）
int func(int n) {
    if (n == 1) return 1;
    return func(n - 1) * n;
}

A. \(O(n^2)\) B. O(n) C. \(O(2^n)\) D. \(O(nlog_2n)\)

解析

答案：B。【解析】递归关系式为T(n)=T(n−1)+O(1)，为什么这里是O（1）不是O（n），因为 * n是单个乘法操作，时间消耗为常数。

展开递归：T(n)=T(n−1)+O(1)=(T(n−2)+O(1))+O(1)=(T(n−3)+O(1))+O(1)+O(1)=...=T(1)+O(n)

因为 T(1) = O(1)，最终得：T(n)=O(n)

  1. 下列递归表达式的复杂度是多少()

\(T\left(n\right)=3T\left(n/4\right)+\Theta\left(n^2\right)\)

A.\(O（n^2）\)
B. \(O（2^n）\)
C. \(O (n)\)
D. \(O（n^2log_2n）\)

解析

答案：A。【解析】
【方法一】递归树法。
展开第一层，我们画出根节点下面的三个子节点。其中，公式表示根节点这一层分解和合并的代价，也就是递归式中公式表示的部分。

这样就得到了一棵完整的递归树。每层数据规模缩小为之前的四分之一，直到叶子结点数据规模为1，因此总层数为公式 。上图最右侧计算了每层所有结点的总代价，计算方式很简单，就是单个结点的代价乘以该层的结点数量。其中，最后一层单个结点的代价为常数，结点数量为公式 ，总代价我们记做公式
接下来，我们只需要把所有结点的代价加起来，就可以得到递归式的解。

公式

【方法二】主定理（直接记结论）
递归表达式形如：公式

  • 公式
  • 公式，且对于某个常数c<1和所有足够大的n有公式,则可以推导出公式
  • 公式，则公式
  • 例题：
    ①公式
    • 对于这个递归式，我们有公式 ,此时公式。由于公式 渐进小于公式,所以可以应用于主定理的第一种情况，从而得到解公式

②公式

    • 对于该式，有公式 ,此时公式,恰好与公式相等，所以可以应用于主定理的第二种情况，从而得到解公式

③公式

    • 对于该式，有公式 ,此时公式 。显然公式渐进大于公式,应考虑主定理的第三种情况。但需要检查是否满足附加条件： 对于某个常数c<1和所有足够大的n有公式。带入a 、b和公式,得公式

当公式 时，该式恒成立，附加条件满足，可以应用主定理的第三种情况，从而得到解公式

④公式

  • 对于该式，有公式 ,此时公式。显然，公式渐进大于n ,应考虑主定理的第三种情况。将其带入附加条件，得

公式

当公式时，该式恒成立。但附加条件要求 c<1 ,因此该式不能使用主方法的第三种情况。也就是说，并非所有形如公式的递归式都可以应用主方法求解，情况二和情况三之间是存在空隙的。这种情况我们就只能采用递归树的方法求解了，同学们可以试一下，求出来的结果为公式