請問助教 我能資結的題目嗎= = Int RecursivesSum(int element[],int n) { If(n) return(RecursiveSum(element,n-1)+element[n-1]); return 0; } (a)Let the time complexity of this function is t(n).Please derive a recursive formula for t(n) indicating the recurrence relation between t(n) and t(n-1).
5 則留言:
1. OK, 這題在chap5的習題的第5-79題有, 因為解出來有很多log, 所以你寫答案時最好稍微括一下括號, 才不會造成混淆
2. 要一步一步慢慢來
30*n^3 is K(n^3) (R1)
7n^2 is K(n^2) (R1)
(logn)^3 is K(n) (R7)
=> 7n^2*(logn)^3 is K(n^2*n)=K(n^3) (R3)
=> 30n^3+7n^2*(logn)^3 is K(n^3+n^3) (R2)
= K(2*n^3)
= K(n^3) (R1)
1.OK 我會再去看習題的
2.原來要慢慢拆解唷
我瞭解了 謝謝助教
請問助教 我能資結的題目嗎= =
Int RecursivesSum(int element[],int n)
{
If(n)
return(RecursiveSum(element,n-1)+element[n-1]);
return 0;
}
(a)Let the time complexity of this function is t(n).Please derive a recursive
formula for t(n) indicating the recurrence relation between t(n) and t(n-1).
不了解
"element[n-1]"
要怎麼寫到遞迴方程式
是T(n)=T(n-1)+n-1
還是只要T(n)=T(n-1)+1 這麼嗎?
且不了解T(n)到什麼時候會結束
是0,n<=0?
可以問但不要問太多, 我會懶得看
這裡的 RecursiveSum 顧名思義就是把陣列裡的元素全部做加總, 只是他是用遞迴的方式來寫而不是用迴圈, 遞迴的時間一般要算的就是執行operation的次數, 所以是 t(n)=t(n-1)+1, 因為當 n=0 時就不會再遞迴下去了, 所以初始值為 t(0)=0
好的 不好意思!
謝謝助教解惑
張貼留言