2014-02-12 62 views
0

我學習的時間複雜度,並且具有這樣的功能:任何人都可以幫助理解一個遞歸關係?

public static double pow(double x, int n) { 
    if(n==0) return 1.0; 
    return x*pow(x,n-1); 
} 

我與發現的遞推關係爲它的時間複雜度和任務我知道答案是T(N)= T(N-1 )+ O(1),我不明白,因爲我認爲它應該是T(n)= T(n-1)+ O(n)。我的推理是,我將每次遞歸調用乘以x發生n次,這就是O(n)正確嗎?

*編輯:我想我明白我的錯誤。 T(n)= T(n-1)+ O(1)僅用於特定的調用,因此它顯然是O(1),解決重複導致n * T(n-1)+(n-1)O (1),所以(n-1)O(1)因爲小於n * T(n-1)而被忽略。所以我們得到增長的秩序= O(n)。

回答

0

您不需要考慮乘法。復發關係是關於一個號碼的呼叫如何與同一呼叫的不同號碼相關。在這種情況下,計算pow(x,n)要求您已知道pow(x,n-1) - 這就是T(n) = T(n-1)部分。現在,你還需要做什麼來計算pow(x,n),因爲你已經有pow(x,n-1)?這只是一個單一的乘法 - x*pow(x,n-1) - 這是O(1),所以總的遞歸關係是T(n) = T(n-1) + O(1)。所有其他的乘法已經在T(n-1) ...

+0

中解釋了,是的,謝謝,我想我只是想通了。 –

相關問題