Re: [問題] 簡單的找最大最小值問題
※ 引述《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
討論串 (同標題文章)