[理工] 104 成大電通 資結

看板Grad-ProbAsk作者 (ㄏㄏ哥)時間8年前 (2018/01/24 15:13), 編輯推噓1(2推 1噓 10→)
留言13則, 4人參與, 7年前最新討論串1/1
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://www.ptt.cc/bbs/Grad-ProbAsk/M.1516778035.A.70C.html
推
01/24 16:05, 8年前 , 1F
key comparison 就是比較次數，exchange 1次表示bubble
01/24 16:05, 1F
→
01/24 16:05, 8年前 , 2F
sort只做2回合，所以比較次數是(n-1)+(n-2) < 2*(n-1)
01/24 16:05, 2F
→
01/24 16:05, 8年前 , 3F
, ture
01/24 16:05, 3F
噓
01/24 16:07, 8年前 , 4F
他題目就跟你說明key是什麼了 然後nondecreasing or
01/24 16:07, 4F
→
01/24 16:07, 8年前 , 5F
der就是 >=的排序 這丟google都有答案 為什麼要上來
01/24 16:07, 5F
→
01/24 16:07, 8年前 , 6F
問
01/24 16:07, 6F
→
01/24 16:08, 8年前 , 7F
non decreasing order就是ascended order
01/24 16:08, 7F
→
01/24 21:45, 8年前 , 8F
謝謝n大跟a大 我原本是想說這個 key comparison跟一般的
01/24 21:45, 8F
→
01/24 21:46, 8年前 , 9F
比較是差在哪里，不過看來應該沒差說想多了@@
01/24 21:46, 9F
→
01/24 21:46, 8年前 , 10F
non-decreasing 我知道是>=但是想說是不是還有其他意思
01/24 21:46, 10F
→
01/24 21:46, 8年前 , 11F
就上來問問看了
01/24 21:46, 11F
推
02/21 16:36, 7年前 , 12F
其實我也不是很懂這題 請問原Po有寫出來嗎 可否提供詳解
02/21 16:36, 12F
→
02/21 16:36, 7年前 , 13F
我也想弄懂這題
02/21 16:36, 13F
‣ 更多 ooxx5626 的文章
文章代碼(AID): #1QQ38pSC (Grad-ProbAsk)