计算递归算法的 Big O 复杂度

Question

不知何故，我发现与迭代算法相比，推导递归算法的 Big 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

您需要做的就是计算基本操作执行了多少次。分析任何一种算法都是如此。对于您的情况，我们将计算 submethod 被调用的次数。

您可以 break-down 运行通话时间 myMethod(n) 为 1 + myMethod(n / 2)。您可以进一步分解为 1 + (1 + myMethod(n / 4))。在某些时候，您将在第 log(n) 步达到基本情况。这为您提供了 log(n).

的算法

第二个没有什么不同，因为 k 一直是常数，它将再次花费 log(n) 时间，假设 submethod 需要常数时间 不管它的输入如何。

Answer 2

对于你的第一个问题，重现将是：

    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))

计算递归算法的 Big O 复杂度

Calculating Big O complexity of Recursive Algorithms

algorithm

recursion

big-o

asymptotic-complexity

code-complexity