[理工] [algo]-找第二小的數

看板Grad-ProbAsk作者 (XD)時間16年前 (2010/03/02 20:25), 編輯推噓3(3推 0噓 15→)
留言18則, 6人參與, 最新討論串1/2 (看更多)
cormen的習題有一題 如何在 n + [log n] - 2 找出第二小的數 看解答看好久不太了解他的意思 為什麼已經偷偷建了tree? 感謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.127.208.96
推
03/02 20:49, , 1F
想像單敗淘汰賽 第二強的就是輸給冠軍的選手裡面最強的..
03/02 20:49, 1F
→
03/02 21:43, , 2F
要是第二強第一輪就再冠軍比 如何得知它是第二強呢@@?
03/02 21:43, 2F
推
03/02 21:47, , 3F
會不是用heap,建heap:O(n),del兩次min:2*O(logn)
03/02 21:47, 3F
→
03/02 21:48, , 4F
不過我不知道它的-2什麼意思
03/02 21:48, 4F
→
03/02 21:50, , 5F
沒有O喔 是確確實實n + [log n] - 2次
03/02 21:50, 5F
→
03/02 21:58, , 6F
應該就1F的答案吧,他指得是"所有"和冠軍比賽過的最強
03/02 21:58, 6F
推
03/02 21:59, , 7F
n個數中 比較n-1次找可找出最小的數
03/02 21:59, 7F
→
03/02 22:01, , 8F
而第2小的數 一定是與剛才最小的數所比輸的其中一個
03/02 22:01, 8F
→
03/02 22:03, , 9F
而最小的數只會比logn(取上限)次 (樹高)
03/02 22:03, 9F
→
03/02 22:04, , 10F
則[log n]個數中 再找出最小須比[log n]-1次
03/02 22:04, 10F
→
03/02 22:06, , 11F
所以total為n-1+[log n]-1=n+[log n]-2
03/02 22:06, 11F
→
03/02 22:10, , 12F
比 [logn] + [lon(n-1)] 次就可以找出第二小的數
03/02 22:10, 12F
→
03/02 22:11, , 13F
題目會給定比的次數，應該是有限定只能用某種邏輯去跑
03/02 22:11, 13F
→
03/02 22:21, , 14F
樓上詳細希望QQ 我想不到[logn] + [lon(n-1)]的方法
03/02 22:21, 14F
→
03/02 23:57, , 15F
就跟 3F 的作法差不多，找 min → 移除min →找min
03/02 23:57, 15F
→
03/02 23:57, , 16F
另外那個是 log , 我打錯成 lon OTZ
03/02 23:57, 16F
→
03/02 23:59, , 17F
有不建heap然後又能logn找到最小的方法?
03/02 23:59, 17F
→
03/03 00:28, , 18F
我耍笨QQ , 我把它跟 divide and conquer 搞混
03/03 00:28, 18F
‣ 更多 yesa315 的文章
文章代碼(AID): #1BZGE-ep (Grad-ProbAsk)
‣ 更多 yesa315 的文章
文章代碼(AID): #1BZGE-ep (Grad-ProbAsk)