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

看板Grad-ProbAsk作者 (billy)時間8年前 (2017/10/28 17:05), 8年前編輯推噓0(0推 0噓 17→)
留言17則, 2人參與, 8年前最新討論串1/1
書籍：洪逸資料結構（五版） 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
→
10/28 20:41, 8年前 , 1F
+1或+2不影響最後的答案
10/28 20:41, 1F
→
10/28 20:48, 8年前 , 2F
10/28 20:48, 2F
→
10/28 20:50, 8年前 , 3F
都是+1或+2都是+常數，也就是+O(1)
10/28 20:50, 3F
→
10/28 21:36, 8年前 , 4F
^^^^多打的
10/28 21:36, 4F
→
10/28 21:58, 8年前 , 5F
n<=2時，T(n)都是O(1)。原題T(2)=T(1)=T(0)=T(-1)....
10/28 21:58, 5F
→
10/28 21:58, 8年前 , 6F
為了要算遞迴式，只能取到T(2)=T(1)=O(1)
10/28 21:58, 6F
→
10/28 21:59, 8年前 , 7F
也就是限制遞迴式只在n>=某些常數時才成立
10/28 21:59, 7F
→
10/28 22:05, 8年前 , 8F
^^^^^^^^1
10/28 22:05, 8F
→
10/28 22:05, 8年前 , 9F
書上的解答，只要再幫遞迴式加上n的下限就好了
10/28 22:05, 9F
→
10/28 22:05, 8年前 , 10F
比方說n>=2，然後再加T(n)=O(1) as n<=2
10/28 22:05, 10F
→
10/29 01:48, 8年前 , 11F
題目在問exact number，解答卻給big-O...
10/29 01:48, 11F
→
10/29 01:51, 8年前 , 12F
解答第二式T(n)跟第一式T(n)不相等，缺一個係數。
10/29 01:51, 12F
→
10/29 02:06, 8年前 , 13F
抱歉，我漏看了exactly
10/29 02:06, 13F
→
10/29 02:21, 8年前 , 14F
所以第二式T(3)=2但T(1)及T(2)=1出現3自己不需operation
10/29 02:21, 14F
→
10/29 02:27, 8年前 , 15F
原PO如果只想算除法和加法數量,n<=2沒有除法加法，應為0
10/29 02:27, 15F
→
10/29 02:29, 8年前 , 16F
或是想把題目解讀成除法加法回傳合計只算1次或算成3次，
10/29 02:29, 16F
→
10/29 02:29, 8年前 , 17F
寫題目前先定義好。
10/29 02:29, 17F
謝謝兩位大大熱心的解惑 我瞭解了 謝謝你們！！ ※ 編輯: bobsonlin (49.215.200.151), 10/29/2017 12:52:10
‣ 更多 bobsonlin 的文章
文章代碼(AID): #1Pz4XWPl (Grad-ProbAsk)