循環函數的運行時間

int foo(int n) 
{ 
    if(n==0) 
     return 1; 
    int sum = 0; 
    for(int i = 0;i < n;i++) 
     sum += foo(n-1); 
    return sum; 
}

最近我在學Big O notation。有人可以給我一個關於如何通過使用大O符號以及如何呈現此函數的運行時來確定此循環函數的運行時的想法。循環函數的運行時間

來源

2017-03-01 CDY

所以想想如果你爲大n運行foo（n）會發生什麼。然後該總和包含n次對foo（n-1）的調用。在遞歸樹的下一層，我們有foo（n-1），我們再次調用n（-1）次foo（n-1-1），但是對於我們樹的n foo（n-1）個分支。我們知道樹的高度爲n，因爲我們必須去foo（n-n）。所以在每個遞歸步驟中，將foo的一個實例轉換爲foo（n-1）的O（n）個實例。

我不確定如果我應該透露答案，因爲它看起來像一個練習，但它似乎退出顯而易見，只需繪製遞歸樹的幾個級別，並找到您的答案。

來源

2017-03-01 11:26:36 gue

假設我假設n = 3，那是你提到的遞歸樹嗎？ http://imgur.com/a/lusID – CDY

不，但接近。考慮for循環，遞歸調用sum + = foo（n-1）不依賴於循環變量i。因此，在樹中的每個節點上，我們分支n次，但每個葉子都用n-1調用。 http://imgur.com/a/K9g8z – gue

謝謝，我明白了。你解釋的很容易理解。 – CDY

循環函數的運行時間

回答

相關問題