※ 引述《mqazz1 (无法显示)》之铭言： : 我是看cormen的演算法 : 现在有一个地方想不通(应该算很基本的问题，但我能力不太好...) : 我的问题是在书中的9.1节 : ---------------------------------------------------------------- : 同时找出最大和最小值 : 有一个数列 n : 每两个数互相比较，小的与目前最小值比，大的与目前最大值比， : 所以每两个元素要比较三次。 把这个步骤叫做 (*) 步骤 : 初始值的设定方法: : 1. n为奇数将最大最小值的初值设为A[0] : 2. n为偶数，将A[0]和A[1]互相比较，大的设为最大值的初值，小的设为最小值的初值 : ------------------------------------------------------------------ : 我的问题在这里..分析总次数 : 1. n为奇数，会执行 3└n/2┘次比较 ----> 怎麽来的? 做了 floor(n/2) 次 (*) 步骤 (由於 n 是奇数, 这其实就是 (n-1)/2 ) 所以共需 3*floor(n/2) 次比较 : 2. n为偶数，会有 3(n-2)/2 次比较， ----> 怎麽来的? 做了 (n-2)/2 次 (*) 步骤 (别忘了这时你是从 A[2] 开始) 所以这里共有 3(n-2)/2 次比较 : 然後总共是 3n/2 - 2 ----> 这边是书上的错误吗? 然後你还得算上一开始 A[0] 和 A[1] 的比较 所以是 3(n-2)/2 + 1 = 3n/2 - 2 : 不好意思， : 看似简单的问题我搞不是很懂.... : 谢谢 -- 'Oh, Harry, dont't you see?' Hermione breathed. 'If she could have done one thing to make absolutely sure that every single person in this school will read your interview, it was banning it!' ---'Harry Potter and the order of the phoenix', P513 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.25.11