[理工] 資結 p.1-52 例16題

[bobsonlin (billy)]

書籍：洪逸資料結構（五版）

p.1-52 例16題的題目與解答：
https://i.imgur.com/SDndcyb.jpg

此題我不太瞭解解答遞迴式為什麼會長這樣，與我自己想的不太一樣，以下是我自己寫的
遞迴式：
https://i.imgur.com/sulEKJD.jpg

我寫這遞迴式的想法是：當 n>2 時，要做除法和加法，一共兩個 operation。接著當 n<
=2時，只需回傳值，所以初值為 1

但若按解答的寫法，在 n>2 時，只有一個 operation，是把除法和加法合起來看嗎？接
著反推解答遞迴式的初值，可發現
T(0)=1, T(1)=1, T(2)=2
這讓我百思不得其解，n=2 時只有回傳值，居然有兩個 operation。

不知道是我對題目有誤解，還是觀念有不正確的地方，想請教版上的大大們

謝謝！！

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.215.200.151
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1509181536.A.66F.html
→ JKLee: +1或+2不影響最後的答案
→ JKLee: https://i.imgur.com/ZEgWm1q.jpg
→ JKLee: 都是+1或+2都是+常數，也就是+O(1)
→ JKLee: ^^^^多打的
→ JKLee: n<=2時，T(n)都是O(1)。原題T(2)=T(1)=T(0)=T(-1)....
→ JKLee: 為了要算遞迴式，只能取到T(2)=T(1)=O(1)
→ JKLee: 也就是限制遞迴式只在n>=某些常數時才成立
→ JKLee:                        ^^^^^^^^1
→ JKLee: 書上的解答，只要再幫遞迴式加上n的下限就好了
→ JKLee: 比方說n>=2，然後再加T(n)=O(1) as n<=2
→ outofyou: 題目在問exact number，解答卻給big-O...
→ outofyou: 解答第二式T(n)跟第一式T(n)不相等，缺一個係數。
→ JKLee: 抱歉，我漏看了exactly
→ outofyou: 所以第二式T(3)=2但T(1)及T(2)=1出現3自己不需operation
→ outofyou: 原PO如果只想算除法和加法數量,n<=2沒有除法加法，應為0
→ outofyou: 或是想把題目解讀成除法加法回傳合計只算1次或算成3次，
→ outofyou: 寫題目前先定義好。
謝謝兩位大大熱心的解惑
我瞭解了
謝謝你們！！
※ 編輯: bobsonlin (49.215.200.151), 10/29/2017 12:52:10