作者mqazz1 (无法显示)
站内Prob_Solve
标题[问题] 简单的找最大最小值问题
时间Fri Apr 23 01:01:07 2010
我是看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
1F：推 ledia:举个例子算算看比较次数就知道, 总共有 [n/2] 组, 每组三次 04/23 09:46
2F：推 ledia:啊 没注意底下有详细解释文了 Orz 04/23 09:54