大O符號 - 遞歸函數

我需要找到這個遞歸算法的複雜性，所以，我有3個遞歸算法，只是想知道它們的大O符號。我想我有這些算法中的2個的解決方案，只是想檢查一下社區。大O符號 - 遞歸函數

int f1(int n) 
{ 
    if (n<= 1) 
     return (1); 
    else 
     return (n *f1(n-1)) 
}

我認爲這是O（n）的解決方案。

int f2 (int n) 
{ 
    if(n<=1) 
     return(1); 
    else 
     return(n*f2(n/2)) 
}

我覺得這個解決方案是爲O（log 2（N））

int f3 
{ 
    int x, i; 
    if(n <= 1) 
     return 1; 
    else 
    { 
     x = f3 (n/2);   
     for(i = 1 ; i <= n ; i++) 
     x++;   
     return x; 
    } 
}

什麼是這個遞歸算法的複雜性，我沒有這個算法的解決方案，能夠你幫我？

來源

2017-09-14 Wolvy

通過「他們的大O符號」，你的意思是他們的時間複雜性或者他們結果的增長順序？ – meowgoesthedog

我認爲你需要時間複雜性。另外，編輯你的函數f3，它不會帶任何參數 –

[Master-Theorem]（https://en.wikipedia.org/wiki/Master_theorem）是解決更復雜的問題的常用方法，像最後一個你的問題。 – Paul

你的前兩個答案是正確的。讓我們分析一下你的第三個問題，每次，n除以2，我們需要加n次n，所以複雜度將是 1 * n + 1 * n/2 + 1 * n/4 + ..... + 1 = n（1 + 1/2 + 1/4 + ...）= O（n）

來源

2017-09-14 15:18:12 codecrazer

@codecrazers answer已經涵蓋了如何逐步計算複雜度。但總的來說，Master-Theorem使問題變得更加簡單。

要開始，讓我們改變這個代碼

進入復發：

int f(int n) 
{ 
    if(n <= 1) 
     1 
    else 
     f(n/2) + θ(n) 
}

所以

T(n) = T(n/2) + θ(n) 
T(n <= 1) = 1

是區分3，從而產生

T(n) = θ(n)

來源

2017-09-14 15:37:03 Paul

大O符號 - 遞歸函數

回答

相關問題