计算递归算法的重大复杂性

Question

以某种方式，我发现与迭代算法相比，很难得出递归算法的大复杂性。确实提供一些有关如何解决这两个问题的见解。

*假定Submethod具有线性复杂性

def myMethod(n)
    if (n>0)
    submethod(n)
    myMethod(n/2) 
    end
end 
def myMethod(k,n)
    if(n>0)
    submethod(k)
    myMethod(k,n/2) 
    end 
end

Answer 1

对于您的第一个问题，复发将为：

    T(n) = n + T(n/2)
    T(n/2) = n/2 + T(n/4)
    ...
    ...
    ...
    T(2) = 2 + T(1)
    T(1) = 1 + T(0) // assuming 1/2 equals 0(integer division)
adding up we get:
    T(n) = n + n/2 + n/4 + n/8 + ..... 1 + T(0)
         = n(1 + 1/2 + 1/4 + 1/8 .....) + k // assuming k = T(0)
         = n*1/(1 - 1/2)  ( sum of geometric series a/(1-r) when n tends to infinity)
         = 2n + k

因此， t（n）= o（n）。请记住，我假设n倾向于无穷大，因为这是我们在渐近分析中所做的。。

对于您的第二个问题，很容易看到，我们每次都执行 k原始操作，直到n变为0 。发生这种情况 log（n）次。因此， t（n）= O（k*log（n））

Answer 2

您需要做的只是计算执行基本操作的次数。分析任何类型的算法都是如此。在您的情况下，我们将计算submethod的次数。

您可以分解myMethod(n)为1 + myMethod(n / 2)的运行时间。您可以进一步分解为1 + (1 + myMethod(n / 4))。在某个时候，您将在log(n)第三步中到达基本情况。这给了您log(n)的算法。

第二个没有什么不同，因为k一直是恒定的，因此它将再次需要log(n)时间，假设submethod持续时间无论其输入如何。