推 tsoahans: 40我和解答一樣 25ce我都是用積分算 01/16 00:45
→ odanaga: 38就每個n/k的list從頭合到尾 O(n)做k次 01/16 00:52
→ sm02188612: 我估想25c展開後的overhead和看成n/(1^2)加到n/(lognl 01/16 02:10
→ sm02188612: ogn)，e用夾的類似證log(n!)=nlogn, 結果(n^2)logn不 01/16 02:10
→ sm02188612: 知是不是 01/16 02:10
→ jerry031181: 25e可用類似証調和數列那樣可以得到原式大於 01/16 07:02
→ jerry031181: (n/2)^2log(n/2)=O(n^2*logn) 01/16 07:04
推 jerry031181: 38.n/k+n/k=2n/k再2n/k+n/k=3n/k..kn/k可time 01/16 07:12
→ jerry031181: T(n)=(k+2)*(k-1)n/k=O(nk) 01/16 07:14
→ jerry031181: 35從0count從最後一格開始擺...被騙了 trace一下沒錯 01/16 07:40
推 jerry031181: X40題沒錯 畫出來會有3棵OBST 01/16 07:47
→ jacklions: obst 那題我畫這樣@@ 01/16 16:17
推 jerry031181: 你少畫一格呀～ 頻率0.30沒畫 01/16 19:35
→ jacklions: 38 40 我懂了 01/16 20:02
→ jacklions: 謝謝大家！ 01/16 20:02
→ jacklions: 那有人知道counting sort 01/16 20:02
→ jacklions: 最後一行為什麼要減一嗎？ 01/16 20:02
→ tedchang102: 因為他是從後面開始排 假設有5個1 第一個1要放在第 01/16 20:12
→ tedchang102: 五格，下次就要從第四格開始放 01/16 20:12
推 tcr1br24: 請問40題的weight是怎麼算的? 3Q 01/16 21:11
推 goldflower: 40題答案是對的嗎@@? 我用表格的確算出2.1 但是我在 01/17 17:01
→ goldflower: 做題目的時候其實直接用猜的 結果.25為根的樹的成本 01/17 17:01
→ goldflower: 可以壓到2.0 是因為有兩點有相同頻率造成的嗎 01/17 17:02
→ jacklions: 40我重算是2.10沒錯 01/17 21:17
→ jacklions: obst要怎麼猜 看不太出來@@ 01/17 21:19
→ jacklions: 考試時算這題好像很不划算 01/17 21:19
推 tsoahans: 上面那題01背包我算比較久 01/17 22:07
推 goldflower: 因為OBST還是一樣是binary search tree 01/17 23:01
→ goldflower: 所以我的猜法就是直接隨便組一棵成本最低的樹 01/17 23:01
→ goldflower: 他以下的選項就能刪掉 然後再從剩下選項中看能湊出 01/17 23:02
→ goldflower: 最低成本是多少 因為二元搜尋樹建很快 比畫表格快 01/17 23:02
→ goldflower: 但是這題就被婊了= = 01/17 23:03
推 goldflower: 所謂成本最低的樹不需要是二元搜尋 而是所有二元樹 01/17 23:06
→ goldflower: 中的最低成本 01/17 23:06
→ jerry031181: OBST還是二元搜尋樹喔～ 01/17 23:37
推 goldflower: 對 所以我是用純二元樹刪下限 然後再用剩下的答案 01/18 00:02
→ goldflower: 湊答案 結果這題我湊出比較小的答案也為二元搜尋樹 01/18 00:03
→ goldflower: 但是跟我用OBST演算法算的不一樣 囧 01/18 00:05
→ goldflower: 以array list存法 .25 .2 .3 .2 .05成本更小為2.0 01/18 00:06
推 jerry031181: 這不是BST阿 .25左邊沒有點了 lv2只會有1個點 01/18 07:10
推 goldflower: 阿我自己畫錯….05放到第四層就對了 那我猜法沒問題 01/18 11:21
→ goldflower: 自己搞笑 囧 01/18 11:21