我學習的時間複雜度,並且具有這樣的功能:任何人都可以幫助理解一個遞歸關係?
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)。
中解釋了,是的,謝謝,我想我只是想通了。 –