algorithm - 计算递归算法的大 O 复杂度

Question

不知何故，我发现与迭代算法相比，递归算法更难推导出大 O 复杂度。请提供一些关于我应该如何解决这两个问题的见解。

*假设子方法具有线性复杂度

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被调用的次数。

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

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