algorithm - 具有Log n重组的主定理

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

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））。如何确定时间复杂度？

最佳答案

有了主定理你就不会了，它只适用于某一形式的重现。你说：
如何理解主定理，算法可以递归地定义为：
但这并不是完全准确的——并不是所有的算法都可以像你展示的那样递归地定义。主定理只适用于那些可以这样定义的情况（更具体地说，关于它可以应用到的所有情况，请参见here）。
对于其他形式，还有其他定理，例如this。