→ onlyeric23:後面是O(1) 前面直接展開 會生出 n+調合 之類的吧 02/14 19:37
→ Jerrynet:@@" 為什麼後面是O(1) ? 02/14 19:41
→ onlyeric23:一步一步代也ok n-1,n-2..etc別太早展開就好 02/14 19:51
→ onlyeric23:可以吞的吞一下 反正是O XD 02/14 19:51
→ kyodaisuki:下面T(n) 我慢慢拆了n-1 n-2.. 感覺應該是O(1) 02/14 19:52
→ kyodaisuki:最後會收斂到一個常數~~ 我意見同一樓 02/14 19:53
推 pikachu123:這題不可能是O(1) 99北大離散有一題跟這題型一樣 02/14 19:55
→ pikachu123:不過他沒加那個 (2n-1)/n 北大那題close form 02/14 19:56
→ pikachu123:O(n^3) 這個應該更大 他後面那個很難搞.... 02/14 19:57
→ pikachu123:我用轉換法用當機了.... 北大那題是用暴力法帶入展開 02/14 19:58
→ pikachu123:這題(2n-1)/n用帶入展開會哭... 02/14 19:59
推 pikachu123:我在猜這個upper bound是O(n^3) 應該他後面那項是常數 02/14 20:02
→ kyodaisuki:我倒認為是 O(n) 因為會多出 n*O(1) 02/14 20:02
→ kyodaisuki:我好善變 ~~ LOL 02/14 20:02
→ pikachu123:然後他的homogeneous Recuren relation是O(n^3) 02/14 20:03
→ kyodaisuki:因為(n+3)/n (2n-1)/n 都可以看成是一個常數 02/14 20:03
→ pikachu123:通解都O(n^3) 特解加通解不可能是低於O(n^3) 02/14 20:04
→ kyodaisuki:一次要是指消掉一個 最後T(n) 會多出N個O(1) 所以O(N) 02/14 20:04
→ pikachu123:我剛剛有說這個遞迴式的通解 是O(n^3) 02/14 20:04
→ pikachu123:現在就是特解算不出來 02/14 20:05
→ Jerrynet:我有想過用生成函數解，似乎會出現積分，然後放棄..orz 02/14 20:10
→ onlyeric23:我是指後面加的部分是O(1) 不過現在看來有的討論orz 02/14 20:13
→ Jerrynet:咦...如果這類型是O(N^3)，那為什麼quick sort是O(nlogn) 02/14 20:13
→ pikachu123:你先把(2n-1)/n拿掉帶入展開 你就會得到O(n^3) 02/14 20:17
→ pikachu123:他(n+3)(n+2)(n+1)會消不掉 02/14 20:19
→ Jerrynet:喔喔~了解了~~那這題我放棄好了=口=" 02/14 20:20
→ Jerrynet:只有前面的話是 (n+3)!/(6*n!) 02/14 20:21
→ Jerrynet:所以是O(n^3) 02/14 20:21
→ onlyeric23:嘖 被擺了一道 感謝p大orz 02/14 20:22
→ Jerrynet:感謝各位<(_ _)> 02/14 20:27
※ 編輯: Jerrynet 來自: 119.14.30.162 (02/14 22:52)