作者ooxx5626 (ㄏㄏ哥)
看板Grad-ProbAsk
標題[理工] 104 成大電通 資結
時間Wed Jan 24 15:13:52 2018
1.When n (n>2) data items are sorted using bubble sort algorithm and the number of key comparison is k, if the number of data item exchanges is 1, then k<=2*(n-1)
這邊不太懂他的key comparison 是什麼意思
下面這裡 不懂他題目中的兩個key是在幹嘛的@@
像第一題找適合的sort into non-decreasing order based on key1 就不知道這個key1是什麼了…
http://i.imgur.com/vuXtkHw.jpg
順便問一下non-decreasing order是指說不在worst case嗎？ 寫題目常常看到
-----
Sent from JPTT on my Sony D6653.
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 117.19.164.233
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1516778035.A.70C.html
1F：推 nova06091: key comparison 就是比較次數，exchange 1次表示bubble 01/24 16:05
2F：→ nova06091: sort只做2回合，所以比較次數是(n-1)+(n-2) < 2*(n-1) 01/24 16:05
3F：→ nova06091: , ture 01/24 16:05
4F：噓 aggress5566: 他題目就跟你說明key是什麼了 然後nondecreasing or 01/24 16:07
5F：→ aggress5566: der就是 >=的排序 這丟google都有答案 為什麼要上來 01/24 16:07
6F：→ aggress5566: 問 01/24 16:07
7F：→ nova06091: non decreasing order就是ascended order 01/24 16:08
8F：→ ooxx5626: 謝謝n大跟a大 我原本是想說這個 key comparison跟一般的 01/24 21:45
9F：→ ooxx5626: 比較是差在哪里，不過看來應該沒差說想多了@@ 01/24 21:46
10F：→ ooxx5626: non-decreasing 我知道是>=但是想說是不是還有其他意思 01/24 21:46
11F：→ ooxx5626: 就上來問問看了 01/24 21:46
12F：推 alily86: 其實我也不是很懂這題 請問原Po有寫出來嗎 可否提供詳解 02/21 16:36
13F：→ alily86: 我也想弄懂這題 02/21 16:36