※ 引述《InitialShuk (Shuk)》之銘言：
: X Y為兩個sorted好的 含n element的array
: 請用O(logN)的algo 找出 X聯集Y之中間值
: 目前只想到O(N) .....
假設X,Y是由小至大排好的array
steps:
1.把X,Y的中間值a,b拿來比較
2.不失其一般性的假設 a < b ，則將X的左半部與Y的右半部刪去。
3.重復 1~2 直到找到中間值
time complexity:
每次皆刪去一半的不可能之情況，所以時間函數為...
T(n) = T(n/2) + O(1)
= O(lg n) //n為X聯集Y之長度
有錯請各位大大更正囉^^
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.229.83.185
※ 編輯: fish0835 來自: 61.229.83.185 (04/09 20:23)