以下函數的增長率是多少

下面的函數在大O符號方面的增長率是多少？以下函數的增長率是多少

f (n) = Comb(1000,n) for n = 0,1,2,… 


int Comb(int m, int n) 
{ 
    int pracResult = 1; 
    int i; 

    if (m > n/2) m = n-m; 

    for (i=1; i<= m; i++) 
    { 
     pracResult *= n-m+i; 
     pracResult /= i; 
     practicalCounter++; 
    } 

    return pracResult; 

}

遞歸：

int combRecursive (int m, int n) 
{ 
    recursiveCounter++; 
    if (n == m) return 1; 
    if (m == 1) return n; 
    return combRecursive(n-1, m) + combRecursive(n-1, m-1); 

}

我猜想N^2 ???我可能是錯誤的，雖然...我一直在努力弄清楚事情是如何有效的...

謝謝先進。

來源

2013-03-09 JLott

我收回我的話。如果你寫的是正確的，你的函數在O（1）中運行。 – 2013-03-09 05:30:26

需要更多信息梳（） – Amitd 2013-03-09 05:33:51

我很抱歉。我會很快更新這個問題。 – JLott 2013-03-09 05:34:42

這是O(1)。

根據定義，f(n) = O(g(n))如果存在c使得對所有n，f(n) <= c*g(n)

讓c = Comb(1000,500)

對於所有n，Comb(1000, n) < c * 1。因此Comb(1000, n) = O(1)

來源

2013-03-09 05:35:08 rici

你真的認爲這是她正在尋找的答案嗎？ :) – 2013-03-09 05:36:59

@Ajeet，我認爲這是提出的問題的答案。令人驚訝的是，人們提出的問題實際上並不期望得到正確的答案。有時甚至會導致他們接受錯誤的答案。這種情況也經常發生在政治領域。 – rici 2013-03-09 05:39:40

哈哈。我更新了代碼。 – JLott 2013-03-09 05:40:28

對於n = 1至2000會有操作與n成比例

對於所有n> 2000，總操作是恆定的。

因此功能複雜度爲O（1）

而且我要告訴你，你得讀一些書。 :)
Sahni的數據結構和算法非常輕讀。 Knuth的算法非常重，但效果最好。

來源

2013-03-09 05:35:57

碼已更新 – JLott 2013-03-09 05:41:01

是啊，我確實很驚訝，哈哈。 – JLott 2013-03-09 05:56:21

謝謝，我會研究它:)算法從來都不是我的東西。當談到他們的時候，我是一個試錯型的人。 – JLott 2013-03-09 05:57:23

以下函數的增長率是多少

回答

相關問題