algorithm - 具有 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))。如何确定时间复杂度？

Answer 1

使用 Master 定理，您不会，它仅适用于某种形式的重复。你说：

我如何理解主定理，算法可以递归定义为：

但这并不完全准确 - 正如您所展示的那样，并非所有算法都可以像这样递归地定义。主定理仅适用于可以这样定义的那些（更具体地说，请参阅此处了解它可以应用于的所有情况）。

对于其他形式，还有其他定理，例如this。