带有Log n重组的主定理

Question

我对主定理的理解是，一个算法可以被递归地定义为：

a T(n/b) + O(n^d)

当a为子问题数量，n/b为子问题的大小，O(n^d)为子问题的重组时间。计算主定理的时间复杂度如下：

T(n) =  { O(n^d)                    if d > log base b of a
        {
        { O(n^d log n)              if d = log base b of a
        {
        { O(n^ (log base b of a) )  if d < log base b of a

我的问题是，如果重新组合时间没有表达为O(n^d)的形式，比如O(2^n)或O(log(n))，那么怎样确定时间复杂度呢？

- Dan Brenner

Answer 1

使用主定理是不行的，因为它只适用于特定形式的递归。你说：

我对主定理的理解是，一个算法可以被递归地定义为：

但这并不完全准确 - 并非所有算法都可以像这样被递归地定义，正如你自己所展示的那样。主定理只适用于可以像这样被定义的算法（更具体地说，请参见此处以了解其适用范围）。

对于其他形式的递归，有其他定理，例如这个。

- IVlad