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 定理不会，它只适用于某种形式的递归。你说:

How I understand the master theorem, an algorithm can be defined recursively as:

但这并不完全准确——并非所有算法都可以像您自己展示的那样递归定义。 Master 定理仅适用于那些可以这样定义的定理(更具体地说，请参阅 here 了解它可以适用的所有情况)。

对于其他形式，还有其他定理，比如this .