計算遞歸算法的大O複雜

不知怎的，我發現，這是更難得出比較迭代算法遞歸算法大O的複雜性。請提供一些關於我應該如何解決這兩個問題的見解。計算遞歸算法的大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

來源

2017-02-21 X.enia

你有沒有嘗試將這些轉換爲迭代算法？它們都是尾遞歸的，並且易於迭代。例如，第一個是'while n> 0 {submethod（n）; N/= 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。發生這種情況日誌（n）次。因此，T（N）= O（K *的log（n））

來源

2017-02-21 06:23:21

是的，我看太感謝你了！我現在對它有了更好的理解 –

所有你需要做的是數的基本操作執行多少次。分析任何類型的算法都是如此。在你的情況下，我們將計算調用次數爲submethod。

你可以擊穿通話myMethod(n)的運行時間是1 + myMethod(n/2)。您可以進一步細分至1 + (1 + myMethod(n/4))。在某些時候，你會到達基本案例，在log(n)的第一步。這給了你一個算法log(n)。

第二個是沒有什麼不同，因爲k是恆定的時候，它會再次採取log(n)時間，假定submethod需要恆定時間不管其輸入的。

來源

2017-02-21 06:10:21

嗯謝謝您的輸入，但是對於第一個答案是〜O（n）和〜Ø（K LOGN）如果我記錯。這就是我的困惑是因爲這2種算法是如何相似的外觀卻不同他們的答案 –

很抱歉的混亂，我認爲'submethod'正在採取一定的時間，而與輸入的... –

計算遞歸算法的大O複雜

回答

相關問題