作者ncdonalds123 (benben)
看板Grad-ProbAsk
標題[理工] 資結 sort找最大,次大,最小
時間Tue Jan 29 21:29:42 2019
https://i.imgur.com/bZGFQOg.jpg
請問第六題
a跟b小題我用bottom up 建max heap最後輸出root這樣可以時間O(n)
c小題我先存頭兩個數字，然後依序讀取，若有大於或小於這兩個數字的swap時間在O(n
)
這樣子寫會有哪裡有問題嗎，還是我完全搞錯題目意思了
麻煩大家了，謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.108.194
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1548768584.A.C75.html
1F：→ moozkito: 他要的是確定的數字吧 01/29 23:44
2F：→ moozkito: 舉例來說用bubble sort跑1iteration，最差比38次可以找 01/29 23:44
3F：→ moozkito: 到最大 不過想不到有什麼更好的 01/29 23:44
4F：推 nannnnn: 我是用遞迴 取前面兩個數相比得兩數a1>a2 然後遞迴下去找 01/30 00:09
5F：→ nannnnn: n-2個數最大最小，再拿大比a1最小比a2，時間複雜度為T(n) 01/30 00:09
6F：→ nannnnn: =T(n-2)+3 01/30 00:09
7F：推 nannnnn: 忘記說c小題 01/30 00:10
8F：→ nannnnn: ab小題我只會線性比38次找到QQT 01/30 00:12
9F：→ ncdonalds123: 謝謝,看來就寫38次了,不知道他到底是想要我們回答 01/30 11:32
10F：→ ncdonalds123: 什麼QQ 01/30 11:32
11F：推 FRAXIS: b 小題不可能 38 吧 01/30 11:50
13F：→ ncdonalds123: 原本b是考慮寫75感謝樓上提供演算法 01/30 17:28
14F：→ nannnnn: 耍二了 第二不可能38 01/31 17:26