[理工] [軟設] 90 台大資工 (也算離散吧?)

看板Grad-ProbAsk作者 (聖石小子)時間14年前 (2012/02/14 19:07), 編輯推噓2(2推 0噓 29→)
留言31則, 5人參與, 最新討論串1/1
第六題： 問Big-O T(n) = n + 4/n * ( T(1)+T(2)+....+T(n-1) ) 這跟quick sort之 avg case的型長得很像，可是我用類似的方法算到 T(n) = (n+3)/n * T(n-1) + (2n-1)/n 之後就不會了，請問有方法可以真的算出解嗎？還是只能求Big-O? 因為我卡在這裡，所以沒有頭緒，只好來請問各位了 <(_ _)> -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 119.14.30.162
→
02/14 19:37, , 1F
後面是O(1) 前面直接展開 會生出 n+調合 之類的吧
02/14 19:37, 1F
→
02/14 19:41, , 2F
@@" 為什麼後面是O(1) ?
02/14 19:41, 2F
→
02/14 19:51, , 3F
一步一步代也ok n-1,n-2..etc別太早展開就好
02/14 19:51, 3F
→
02/14 19:51, , 4F
可以吞的吞一下 反正是O XD
02/14 19:51, 4F
→
02/14 19:52, , 5F
下面T(n) 我慢慢拆了n-1 n-2.. 感覺應該是O(1)
02/14 19:52, 5F
→
02/14 19:53, , 6F
最後會收斂到一個常數~~ 我意見同一樓
02/14 19:53, 6F
推
02/14 19:55, , 7F
這題不可能是O(1) 99北大離散有一題跟這題型一樣
02/14 19:55, 7F
→
02/14 19:56, , 8F
不過他沒加那個 (2n-1)/n 北大那題close form
02/14 19:56, 8F
→
02/14 19:57, , 9F
O(n^3) 這個應該更大 他後面那個很難搞....
02/14 19:57, 9F
→
02/14 19:58, , 10F
我用轉換法用當機了.... 北大那題是用暴力法帶入展開
02/14 19:58, 10F
→
02/14 19:59, , 11F
這題(2n-1)/n用帶入展開會哭...
02/14 19:59, 11F
推
02/14 20:02, , 12F
我在猜這個upper bound是O(n^3) 應該他後面那項是常數
02/14 20:02, 12F
→
02/14 20:02, , 13F
我倒認為是 O(n) 因為會多出 n*O(1)
02/14 20:02, 13F
→
02/14 20:02, , 14F
我好善變 ~~ LOL
02/14 20:02, 14F
→
02/14 20:03, , 15F
然後他的homogeneous Recuren relation是O(n^3)
02/14 20:03, 15F
→
02/14 20:03, , 16F
因為(n+3)/n (2n-1)/n 都可以看成是一個常數
02/14 20:03, 16F
→
02/14 20:04, , 17F
通解都O(n^3) 特解加通解不可能是低於O(n^3)
02/14 20:04, 17F
→
02/14 20:04, , 18F
一次要是指消掉一個 最後T(n) 會多出N個O(1) 所以O(N)
02/14 20:04, 18F
→
02/14 20:04, , 19F
我剛剛有說這個遞迴式的通解 是O(n^3)
02/14 20:04, 19F
→
02/14 20:05, , 20F
現在就是特解算不出來
02/14 20:05, 20F
→
02/14 20:10, , 21F
我有想過用生成函數解，似乎會出現積分，然後放棄..orz
02/14 20:10, 21F
→
02/14 20:13, , 22F
我是指後面加的部分是O(1) 不過現在看來有的討論orz
02/14 20:13, 22F
→
02/14 20:13, , 23F
咦...如果這類型是O(N^3)，那為什麼quick sort是O(nlogn)
02/14 20:13, 23F
→
02/14 20:17, , 24F
你先把(2n-1)/n拿掉帶入展開 你就會得到O(n^3)
02/14 20:17, 24F
→
02/14 20:19, , 25F
他(n+3)(n+2)(n+1)會消不掉
02/14 20:19, 25F
→
02/14 20:20, , 26F
喔喔~了解了~~那這題我放棄好了=口="
02/14 20:20, 26F
→
02/14 20:21, , 27F
只有前面的話是 (n+3)!/(6*n!)
02/14 20:21, 27F
→
02/14 20:21, , 28F
所以是O(n^3)
02/14 20:21, 28F
→
02/14 20:22, , 29F
嘖 被擺了一道 感謝p大orz
02/14 20:22, 29F
→
02/14 20:27, , 30F
感謝各位<(_ _)>
02/14 20:27, 30F
※ 編輯: Jerrynet 來自: 119.14.30.162 (02/14 22:52)
→
09/11 14:56, , 31F
通解都O(n^3) 特 https://daxiv.com
09/11 14:56, 31F
‣ 更多 Jerrynet 的文章
文章代碼(AID): #1FEa1LOS (Grad-ProbAsk)