計算一個Recusive算法的時間複雜度

我想計算一個遞歸算法的時間複雜度，我想我已經差不多了。這是我一直在尋找的僞代碼：計算一個Recusive算法的時間複雜度

long pow(long x, int n) { 
    if (n == 0) 
     return 1; 
    if (n == 1) 
    return x; 
    if(isEven(n)) 
     return pow(x, n/2) * pow(x, n/2); 
    else 
     return x * pow(x * x, n/2); 
}

ISEVEN只是決定傳遞給它的整數是否是偶數還是沒有，在這個例子中的點，在固定時間內進行操作。因此，如果n = 0或n = 1，它就運行它，它有恆定的時間操作，如下所示： f（n）= C0。然而，當n> 1時，它應該像這樣操作：當n是偶數並且f（n）= f（n-1）時，f（n）= f（n-1）+ f（n-1）+ C1 ）+ n當n是奇數時，是正確的？或者應該是：當n是偶數時，f（n）= f（n/2）+ f（n/2）+ C1，當n是奇數時，f（n）= f（n/2）+1。

我一直在看很多的例子。 Here是我發現非常有幫助的一個。我的問題源於當n是偶數時有兩個遞歸調用 - 我不完全確定在這裏做什麼。如果任何人都可以指出我正確的方向，我會很感激。

來源

2011-02-01 thomascirca

請允許我歡迎你們來的StackOverflow，並提醒三件事，我們通常在這裏做的：1）當你得到幫助，儘量給它太**回答問題**你專業2的面積）[`閱讀FAQs` （http://tinyurl.com/2vycnvr）3）當你看到很好的Q＆A，投起來[`採用灰色triangles`（http://i.imgur.com/kygEP.png），作爲信譽該系統的基礎是用戶通過分享知識獲得的聲譽。還請記住接受更好地解決您的問題的答案，如果有的話，['通過按複選標記符號]（http://i.imgur.com/uqJeW.png） – 2011-02-01 04:24:18

這個新手問題很好。 – sharptooth 2011-02-01 13:00:21

看看Master Theorem。您可以將其視爲「分而治之」算法。

最終的結果是，通過兩次遞歸調用，最終會導致最壞情況的O（n）運行時。例如。 pow（x，4）兩次調用pow（x，2），pow（x，1）四次;一般來說，2的冪次將導致n * 2-1個呼叫。

另請注意，只需調用pow（x，n/2）一次並將結果放在該分支中，算法就變爲O（log n）。

來源

2011-02-01 02:43:17

讓我們定義f（m），因爲它給出了大小爲m的問題的運算次數。 '問題'當然是指數（pow），如x^n或pow(x,n)。如果我更改x，long pow(long x, int n) {函數不需要做更多或更少的工作。所以，問題求冪的大小並不取決於x。但它取決於n。比方說，2^4的大小爲4和3^120是尺寸120的尺寸問題由此等於n，第二個參數（如果你看到2^4=2*2*2*2和3^120=3*3*3*3*..*3有道理）。如果你願意的話，我們可以說問題的大小是2 * log（n），但這很愚蠢。

現在我們有f（m）是任何x的計算pow(x,m)的操作數。因爲pow(x,m)正是大小爲m的問題。 因此，如果我們有pow(x,y)那麼根據定義，操作次數爲f(y)。例如，pow(3,3*m/2)有f(3*m/2)操作。

最後，讓我們來算的操作

long pow(long x, int n) { 
    if (n == 0) //1 
     return 1; 
    if (n == 1) //1 
    return x; 
    if(isEven(n)) //1 
     return pow(x, n/2) * //that is f(n/2), y=n/2 
       pow(x, n/2); //also f(n/2) 
    else 
     return x * pow(x * x, n/2); //1+1+f(n/2) 
}

把它一起：f(n) = 2*f(n/2) + c1（n爲偶數）和f(n) = f(n/2) + c2（n爲奇數）。如果你只對最壞的情況感興趣，那麼請注意，奇怪的情況是較少的工作。因此，f（n）受以上情況的限制：f(n) <= 2*f(n/2)+c。

來源

2011-02-01 12:57:54 Ishtar

計算一個Recusive算法的時間複雜度

回答

相關問題