推 ledia:舉個例子算算看比較次數就知道, 總共有 [n/2] 組, 每組三次 04/23 09:46
推 ledia:啊 沒注意底下有詳細解釋文了 Orz 04/23 09:54
我是看cormen的演算法
現在有一個地方想不通(應該算很基本的問題，但我能力不太好...)
我的問題是在書中的9.1節
----------------------------------------------------------------
同時找出最大和最小值
有一個數列 n
每兩個數互相比較，小的與目前最小值比，大的與目前最大值比，
所以每兩個元素要比較三次。
初始值的設定方法:
1. n為奇數將最大最小值的初值設為A[0]
2. n為偶數，將A[0]和A[1]互相比較，大的設為最大值的初值，小的設為最小值的初值
------------------------------------------------------------------
我的問題在這裡..分析總次數
1. n為奇數，會執行 3└n/2┘次比較 ----> 怎麼來的?
2. n為偶數，會有 3(n-2)/2 次比較， ----> 怎麼來的?
然後總共是 3n/2 - 2 ----> 這邊是書上的錯誤嗎?
不好意思，
看似簡單的問題我搞不是很懂....
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.228.31.231