推 FRAXIS:想像單敗淘汰賽 第二強的就是輸給冠軍的選手裡面最強的.. 03/02 20:49
→ yesa315:要是第二強第一輪就再冠軍比 如何得知它是第二強呢@@? 03/02 21:43
推 bensome0624:會不是用heap,建heap:O(n),del兩次min:2*O(logn) 03/02 21:47
→ bensome0624:不過我不知道它的-2什麼意思 03/02 21:48
→ yesa315:沒有O喔 是確確實實n + [log n] - 2次 03/02 21:50
→ bensome0624:應該就1F的答案吧,他指得是"所有"和冠軍比賽過的最強 03/02 21:58
推 lightergogo:n個數中 比較n-1次找可找出最小的數 03/02 21:59
→ lightergogo:而第2小的數 一定是與剛才最小的數所比輸的其中一個 03/02 22:01
→ lightergogo:而最小的數只會比logn(取上限)次 (樹高) 03/02 22:03
→ lightergogo:則[log n]個數中 再找出最小須比[log n]-1次 03/02 22:04
→ lightergogo:所以total為n-1+[log n]-1=n+[log n]-2 03/02 22:06
→ doom8199:比 [logn] + [lon(n-1)] 次就可以找出第二小的數 03/02 22:10
→ doom8199:題目會給定比的次數，應該是有限定只能用某種邏輯去跑 03/02 22:11
→ zkdzvy22:樓上詳細希望QQ 我想不到[logn] + [lon(n-1)]的方法 03/02 22:21
→ doom8199:就跟 3F 的作法差不多，找 min → 移除min →找min 03/02 23:57
→ doom8199:另外那個是 log , 我打錯成 lon OTZ 03/02 23:57
→ zkdzvy22:有不建heap然後又能logn找到最小的方法? 03/02 23:59
→ doom8199:我耍笨QQ , 我把它跟 divide and conquer 搞混 03/03 00:28