作者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/cn.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