為什麼這篇費氏 數列 樹鄉民發文收入到精華區：因為在費氏 數列 樹這個討論話題中，有許多相關的文章在討論，這篇最有參考價值！作者yunruo (I won't give up)看板Grad-ProbAsk標題[商管]...
各位晚安
有一問題如下
請大家幫忙
Arecursive Fibonacci function is defined as：
int F(int n) {
if( n == 0 ) return 0;
if( n == 1 ) return 1;
if( n == 2 ) return 2;
return (F(n-3) - F(n-2)+F(n-1));
}
Please analysis the space complexity of the F function.
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 1.175.163.127
→ ab170926:T(n)=T(n-1)+T(n-2)+T(n-3) 然後解遞迴關係 01/21 19:55
→ ab170926:喔 看錯了 原來是空間複雜度 01/21 19:55
推 lachu:O(n) 01/21 20:32
請問怎麼求來的呢?
※ 編輯: yunruo 來自: 1.175.163.127 (01/21 20:38)
→ lachu:function call會形成一個tree的結構 01/21 20:55
→ lachu:n>=3的children是n-1, n-2, n-3 n<=2就是leaf 01/21 20:56
→ lachu:記憶體中只有從root到現在執行到的node的path 01/21 20:58
→ lachu:其他的部分都是已經return或是還沒執行到的 01/21 20:59
謝謝樓上的解答喔!
※ 編輯: yunruo 來自: 1.175.163.127 (01/22 00:05)