PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 簡單的找最大最小值問題

看板Prob_Solve (計算數學 Problem Solving)作者LPH66 ((short)(-15074))時間14年前 (2010/04/23 01:53)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串2/2 (看更多)

※ 引述《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